| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 1914 | Accepted: 747 |
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
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.
Output
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官方题解
代码实现：
#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; }