Vijos 1331 看球的巴士 解题报告

推出状态转移方程不难，用f[i]表示到第i个人为止最少需要多少辆车，则f[i]=min(f[i],f[j]+1)(0<=j<=i-1)。关键在于如何快速判断能否从一个状态转移到下一个状态，也即快捷地表示出题目中的限制条件。这里介绍一个很巧妙的方法，用g[i]表示到第i个人为止h与j的人数差，显然当abs(g[i]-g[j])=i-j时即从第j+1个人到第i个人中间没有另一球队的球迷。而abs(g[i]-g[j])<=d时即从第j+1个人到第i个人中间，不同球队的球迷的相差人数不大于d。

另外需要注意的是第j+1个人到第i个人不能坐同一辆车不代表第j个人到第i个人不能做同一辆车。

R1128841 Accepted 100 From IwfWcf－ P1331 FPC Vijos Dolphin 2009-2-2 1:05:11