| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 1645 | Accepted: 675 |
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
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
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int m, p, a[305], b[305]; int f[305], before[305]; int main() { scanf("%d%d", &m, &p); for (int i = 1; i <= p; ++i) scanf("%d%d", &a[i], &b[i]); before[0] = a[0] = 300005; f[0] = 1; for (int i = 1; i <= p; ++i) { int suma = 0, sumb = 0; f[i] = f[i - 1] + 2; before[i] = b[i]; for (int j = i; j >= 1; --j) { suma += a[j]; sumb += b[j]; if (suma > m || sumb > m) break; if (suma + before[j - 1] <= m && f[j - 1] + 1 <= f[i]) { if (f[j - 1] + 1 == f[i]) before[i] = min(before[i], sumb); else before[i] = sumb; f[i] = f[j - 1] + 1; } if (suma + before[j - 1] > m && f[j - 1] + 2 <= f[i]) { if (f[j - 1] + 2 == f[i]) before[i] = min(before[i], sumb); else before[i] = sumb; f[i] = f[j - 1] + 2; } } } printf("%d\n", f[p]); return 0; }
原文：http://www.cnblogs.com/albert7xie/p/4840859.html