11D:猴子摘桃

总时间限制:: 10000ms
内存限制:: 65536kB

描述

一只猴子正在赶路，发现了一排桃树。它想去摘桃子，但桃树上可能有马蜂。幸好它带着一罐蜂蜜。每次它接近一个桃树时，只要给树上的每只马蜂一克蜂蜜，就可以放心经过和摘桃，不用担心了被蜇，否则就过不了这棵树且会蜇。幸运的是，猴子可以直接跳到任意一颗桃树开始采摘，然后就只能沿着桃树所在的直线单向走且不可跳过桃树，一旦离开桃树所在的直线就不能再回去。请问被马蜂蜇之前，猴子最多可以摘到多少桃子。

输入

包含多个案例。每个案例的第一行是一个正整数，表示猴子所带蜂蜜的重量，单位为克，接着若干行，每行两个整数，分别表示一颗桃树上的桃子数量和马蜂数量，每个案例的最后一行是两个-1。排在前面的桃树先输入。输入的最后一行是-1。(桃树的数量最大为100)

输出

每个案例输出一个整数，表示猴子被马蜂蛰之前可以摘到的最大桃子数。

样例输入

样例输出

提示

输入数据确保输入数据和计算结果均可表示为4字节的整数。

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 int p[105];
 5 int pp[105][105];
 6 int b[105];
 7 int bb[105][105];
 8 int main(){
 9     int k;
10     while(1){
11         cin>>k;
12         int peach, bee;
13         if(k==-1) return 0;
14         memset(p,0,sizeof(p));
15         memset(pp,0,sizeof(pp));
16         memset(b,0,sizeof(b));
17         memset(bb,0,sizeof(bb));
18         int i, j, n = 1;
19         while(1){
20             cin>>peach>>bee;
21             if(peach==-1&&bee==-1) break;
22             p[n] = peach;
23             b[n++] = bee;
24         }
25         n--;
26         for(i = 1; i <= n; i++){ //前缀和 
27             p[i]+=p[i-1]; 
28             b[i]+=b[i-1];
29         }
30         for(i = 1; i <= n; i++){
31             for(j = i; j <= n; j++){
32                 pp[i][j] = p[j]-p[i-1];
33                 bb[i][j] = b[j]-b[i-1];
34             }    
35         } 
36         int ans = 0;
37         for(i = 1; i <= n; i++){
38             for(j = i; j <= n; j++){
39                 if(bb[i][j]<=k) ans=max(ans,pp[i][j]);
40             }    
41         } 
42         cout<<ans<<endl;
43     }
44     return 0;
45 }