【题意】给定n道题，每月末发放工资m，要求从1解到n，每道题需要在当月初付费ai,下月初付费bi，多道题可以安排在同月，求最少月数。

【算法】DP

【题解】参考自： by 

因为当月的选择同时关系着当月和下月，贪心是错误的，有如下反例：

50 5  

40 10  

10 40  

10 5  

10 3  

10 2

因此考虑DP，令f[i][j]表示解决1~i题，最后一月解决j题的最小月数。（只保证满足当月开销，也就是下月开销之后再算）

sumA(i-j+1~i)<=m

f[i][j]=f[i-j][k]+1,sumB(i-j-k+1~i-j)+sumA(i-j+1~i)<=m

f[i][j]=f[i-j][k]+2,sumB(i-j-k+1~i-j)<=m

两式取小。

复杂度O(n^3)。

注意：初值全局设为inf，中间取min！

#include
      
       #include
       
        #include
        
         using namespace std;const int maxn=310;int f[maxn][maxn],n,m,suma[maxn],sumb[maxn],ans;int main(){    scanf("%d%d",&m,&n);    int u,v;    for(int i=1;i<=n;i++){        scanf("%d%d",&u,&v);        suma[i]=suma[i-1]+u;        sumb[i]=sumb[i-1]+v;    }    memset(f,0x3f,sizeof(f));//    f[0][0]=1;    for(int i=1;i<=n;i++){        for(int j=1;i-j>=0;j++){            for(int k=0;i-j-k>=0;k++)if(suma[i]-suma[i-j]<=m){                if(sumb[i-j]-sumb[i-j-k]<=m)f[i][j]=min(f[i][j],f[i-j][k]+2);//                if(sumb[i-j]-sumb[i-j-k]+suma[i]-suma[i-j]<=m)f[i][j]=min(f[i][j],f[i-j][k]+1);//            }        }            }    ans=0x3f3f3f3f;    for(int j=1;n-j>=0;j++)if(sumb[n]-sumb[n-j]<=m)ans=min(ans,f[n][j]+1);    printf("%d",ans);    return 0;}