解题 (HGOI 2019.2.16 T3)

## 题目大意  ## 数据范围 n<=300,m<=1000 ### 解法 小小的一道DP打错了orz 一开始还以为是一道贪心题，后然发现不行的说。。 ``` 80 90 10 90 90 10 ``` 这样贪心的话显然是要6个月的，但是，2、3合并的话，只用5个月 dp[i][j]=k，表示第i月，完成了j个任务，本月剩余k元 ``` #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m,a[310],b[310]; int dp[310][310]; int main() { memset(dp,-1,sizeof(dp)); scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%d%d",&a[i],&b[i]); dp[1][0]=m; for(int i=1;i<=n;i++) for(int j=0;j<=n;j++) { if(dp[i][j]<0) break; int res1=dp[i][j],res2=m; dp[i+1][j]=max(dp[i+1][j],m); for(int k=j+1;k<=n;k++) { if(res1-a[k]<0 || res2-b[k]<0) break; res1-=a[k],res2-=b[k]; dp[i+1][k]=max(dp[i+1][k],res2); } } int ans; for(int i=1;i<=2*n;i++) if(dp[i][n]!=-1) {ans=i;break;} printf("%d",ans+1); return 0; } ```