分类：
2008-07-19 02:36:20
Time Limit: 2000MS Memory Limit: 65536K
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.
该题目采取动态规划（dynamic programming）解决。
int fb,fa,lb,la,months;
pst[i][j]=min{pst[i][k] merge pst[k+1][j]} (i<=k<=j)
for i=0 to p-r-1
pst[i][i] merge p[i+1][i+r]
if pst[i][k] merge p[k+1][i+r] cost months less than current one
replace it
int fb,fa,lb,la,months;
//fb and fa are the first two payments of the problem chain
//lb and la are the last two payments of the problem chain
//months is the cost of the problem chain
//if they can be merged overlaying 2 month
&& pst[i][k].la+pst[k+1][i+r].fa<=m)
//to amend
//if they can be merged overlaying 1 month
else if(pst[i][k].la+pst[k+1][i+r].fb<=m)
//to amend
//they can be merged overlaying 0 month
return result;
int r,i,k,temp[5];
//r is the len of problems
//i is the first problem
//k is the break point
//thus,merge i~k and (k+1)~(i+r)
//temp use to receive the return of merge()
//temp[0] is b,temp[1] is a,temp[2] is months
//write the case that k=i in the table
//when the months in this case less than the current months,replace it
return pst[0][p-1].months+1;
//because the first month has no money, we have to +1
int i;
scanf("%d %d",&m,&p);
scanf("%d %d",&pst[i][i].fb,&pst[i][i].fa);
return 0;
Sample Input
Sample Output
Sample Input
1 86
Sample Output
