POJ 3265 Problem Solving 动态规划

Problem Solving

Description

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.

Input

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

Output

Line 1: The number of months it takes to solve and pay for all the cows' problems.

Sample Input

100 5 40 20 60 20 30 50 30 50 40 40

Sample Output

6

Hint

+------+-------+--------+---------+---------+--------+ |      | Avail | Probs  | Before  | After   | Candy  | |Month | Money | Solved | Payment | Payment | Money  | +------+-------+--------+---------+---------+--------+ | 1    | 0     | -none- | 0       | 0       | 0      | | 2    | 100   | 1, 2   | 40+60   | 0       | 0      | | 3    | 100   | 3, 4   | 30+30   | 20+20   | 0      | | 4    | 100   | -none- | 0       | 50+50   | 0      | | 5    | 100   | 5      | 40      | 0       | 60     | | 6    | 100   | -none- | 0       | 40      | 60     | +------+-------+--------+---------+---------+--------+

Source

​​USACO 2007 January Gold​​

算法分析

​​USACO官方题解​​

代码实现：

#include<cstdio>  
#include<cstring>  
#include<cstdlib>  
#include<cctype>  
#include<cmath>  
#include<iostream>  
#include<sstream>  
#include<iterator>  
#include<algorithm>  
#include<string>  
#include<vector>  
#include<set>  
#include<map>  
#include<stack>  
#include<deque>  
#include<queue>  
#include<list>  
using namespace std;  
const double eps = 1e-8;  
typedef long long LL;  
typedef unsigned long long ULL;  
const int INT_INF = 0x3f3f3f3f;  
const int INT_M_INF = 0x7f7f7f7f;  
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;  
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;  
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};  
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};  
const int MOD = 1e9 + 7;  
const double pi = acos(-1.0);  
const int MAXN = 1e5 + 10;  
const int MAXT = 10000 + 10;  
const int N=305;
int dp[N],cp[N],a[N],b[N],m,p;
//dp[i]:前i道题的最少月数；
//cp[j]:前j道题的月数最少时，最后一个月支付的钱
int main()  
{  
    while(scanf("%d%d",&m,&p)!=EOF)  
    {  
        
         for(int i=1;i<=p;i++)
            scanf("%d%d",&a[i],&b[i]);
    
    dp[0]=1;
    memset(cp,0,sizeof(cp));
    for(int i=1;i<=p;i++)
    {
        dp[i]=INT_INF;
        int x=a[i],y=b[i];
        for(int j=i-1;j>=0&&x<=m&&y<=m;j--)  //j前面的在上个月或之前完成，j到i的题在本月完成
        {
            int z=dp[j]+2-(cp[j]<=m-x);
             //若付完第i题剩余的钱(m-x)可以支付记录的做完前j题的最后一个月月末付款的最小值(cp[j])，则只需要1个月，否则2个月。
            if(z<dp[i]||(z==dp[i]&&cp[i]>y))//有大于一种情况时，记录最后一个月月末付款的最小值
                
            {
                dp[i]=z;
                cp[i]=y;
                
            }
            x+=a[j];
            y+=b[j];
        }
        
    }  printf("%d\n",dp[p]+1);
    }
    return 0;  
      
}