[bzoj1700]： [Usaco2007 Jan]Problem Solving 解题

　　不能贪心!不能贪心！不能贪心！

　　反正有反例（有的题目月初支付款很少，月末支付款很大，和前面的题凑到一个月的话可能导致下个月写不了= =这时放后一个月，和后面的题一起开始写可能更优）

　　比如：

50 4
40 1
5 10
43 30
1 10

　　老老实实DP吧。。。f[i][j]表示在第i月过后，共解决了j道题，第i月结余（可用于下个月的月初支付）的最大值。cost0[]、cost1[]分别表示月初支付和月末支付

　　f[i][j]=max{m-sum(cost1[k+1]....cost1[j])}，（前提是sum(cost0[k+1]....cost0[j])<=f[i-1][k]且sum(cost1[k+1]....cost1[j])<=m）。

　　数组滚动一下。。。时间复杂度O(P^3)

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 using namespace std;

 const int maxn=;

 int a[maxn],b[maxn],prea[maxn],preb[maxn];

 short f[][maxn];

 int i,j,k,n,m,pre,now,nowrest,next,s1,s2,ans;

 bool flag;

 int ra;char rx;

 inline int read(){

     rx=getchar();ra=;

     while(rx<''||rx>'')rx=getchar();

     while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra;

 }

 int main(){

     m=read();n=read();

     for(i=;i<=n;i++)a[i]=read(),b[i]=read(),prea[i]=prea[i-]+a[i],preb[i]=preb[i-]+b[i];

     nowrest=m;ans=;

     memset(f[],,(n+)<<);f[][]=m;pre=;now=;

     while(){

         ans++;

         memset(f[now],,(n+)<<);

         for(i=;i<=n;i++){

             flag=;

             for(j=i;j>=&&preb[i]-preb[j]<=m;j--)

                 if(prea[i]-prea[j]<=f[pre][j]){f[now][i]=m-preb[i]+preb[j];flag=;break;}

             if(!flag)break;

         }

         if(i>n)break;

         swap(now,pre);

     }

     printf("%d\n",ans+);

     return ;

 }