[USACO 2007 Jan G]Problem Solving

In easier times, Farmer John's cows had no problems. These days, though, they have problems, lots of problems; they have P (1 ≤ P ≤ 300) problems, to be exact. They have quit providing milk and have taken regular jobs like all other good citizens. In fact, on a normal month they make M (1 ≤ M ≤ 1000) money.
Their problems, however, are so complex they must hire consultants to solve them. Consultants are not free, but they are competent: consultants can solve any problem in a single month. Each consultant demands two payments: one in advance (1 ≤ payment ≤ M) to be paid at the start of the month problem-solving is commenced and one more payment at the start of the month after the problem is solved (1 ≤ payment ≤ M). Thus, each month the cows can spend the money earned during the previous month to pay for consultants. Cows are spendthrifts: they can never save any money from month-to-month; money not used is wasted on cow candy.
Since the problems to be solved depend on each other, they must be solved mostly in order. For example, problem 3 must be solved before problem 4 or during the same month as problem 4.
Determine the number of months it takes to solve all of the cows' problems and pay for the solutions.

Line 1: Two space-separated integers: M and P.
Lines 2..P+1: Line i+1 describes problem i with two space-separated integers: Bi and Ai. Bi is the payment to the consult BEFORE the problem is solved; Ai is the payment to the consult AFTER the problem is solved.

#include<bits/stdc++.h> using namespace std; const int N=300; const int M=200; const int mod=1e9+7; const int INF=0x3f3f3f3f; int m,n,a[N+10],b[N+10],dp[N+10][N+10]; int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>m>>n; for(int i=1;i<=n;i++){ int x,y;cin>>x>>y; a[i]=a[i-1]+x,b[i]=b[i-1]+y; } memset(dp,0x3f,sizeof(dp)); dp[0][0]=0; for(int i=1;i<=n;i++){ for(int j=1;j<=i;j++){ if(a[i]-a[i-j]>m || b[i]-b[i-j]>m)continue; for(int k=0;k<=i-j;k++){ if(a[i]-a[i-j]+b[i-j]-b[i-j-k]>m)continue; dp[i][j]=min(dp[i][j],dp[i-j][k]+1); } } for(int j=1;j<=i;j++)dp[i][0]=min(dp[i][j]+1,dp[i][0]); } int ans=INF; for(int i=1;i<=n;i++)ans=min(ans,dp[n][i]+2); ans=min(ans,dp[n][0]+1); cout<<ans; return 0; }

详情