三维DP狂<被>虐费用流!!!

SLF优化真·赞

第⑨个点略坑爹，set判重也是醉了

解方程组分分钟……搜什么搜啊- -
——————战神哥

ls题解看不懂

竟然有人用IO挂刷榜，不能忍！

♂

@2297
其实二分就好了- -

数据有误- -

第3和第10个点答案有问题，应该是无解

表示匈牙利挺快的，同时膜拜前方pascal写dinic比我快的

spfa+多路增广
把dinic改改就好了

为什么RE？返回值是2，找不到输入文件？？@cstdio @常可神牛

pascal代码效率不敢恭维，我都把矩阵搞成这样了才能卡时过，ms我还是这题第一个用pascalAC的

显然m>n+3时无解
考虑女生不相邻：(n+2)!*m!*C(n+3,m)
考虑女生不相邻且老师相邻：2*(n+1)!*m!*C(n+2,m)
二式相减，化简得：Answer=[(n+1)!*(n+2)*(n+1)*...*(n-m+4)]*[(n+2)*(n+3)-2*(n-m+3)]
压4位高精乘，秒之O(∩_∩)O~~

题目有什么蹊跷吗？我在tyvj交过了，在这就是错几个点，@cstdio 求过法

先设一个f[i]表示恰好走i步且不经过已走的点 共有的走法。
如果向上走，不会出现经过已走的点；如果向左或右，上一步不能是向右或左。
这一步的选择数= (3*上一步的所有选择中向上走的选择数) + (2*上一步的所有选择中向左、右走的选择数)。
上一步的所有选择中向上走的选择数”实际上就是“上上步的所有选择数”即f[i-2]
“上一步的所有选择中向左、右走的选择数” 等于 “上步所有的选择数(即f[i-1])-上步向上的选择数”
也就等于 “上步所有的选择数(即f[i-1])-上上步所有的选择数(即f[i-2])”
所以得到递推式：f[i] = (3*f[i-2]) + 2*(f[i-1]-f[i-2]);

最后一个点答案-1，如果从s到t搜会超时TAT，但是从t到s搜就无压力了~

单调栈~~单调栈~~O(n)

第一次写堆dijkstra，结果被spfa血虐- -