Vijos 1322 解题 解题报告

一开始想当然地认为是贪心，于是贡献了一次WA。给出一个贪心的反例数据：

50 5
40 10
10 40
10 5
10 3
10 2

答案应该是4，而贪心由于会把前两道题安排在同一个月解决，会造成要多工作一个月来支付后3题。

用f[i,j]表示最后一个月解决的题目是i到j，则状态转移方程f[i,j]=min(f[i,j],f[k,i-1]+1)(sum_a[j]-sum_a[i-1]+sum_b[i-1]-sum_b[k-1]<=m),min(f[i,j],f[k,i-1]+2)(sum_a[j]-sum_a[i-1]+sum_b[i-1]-sum_b[k-1]>m)

当然，状态转移的前提条件还有其本身是一个有效状态（即月结不能超过m）。

R1126414 Accepted 100 From IwfWcf－ P1322 FPC Vijos Dolphin 2009-1-30 21:17:34