呵呵，这个是背包问题：
/* ID: qq104801 LANG: C++ TASK: inflate */ #include <iostream> #include <fstream> #include <cstring> #include <vector> #include <list> #include <set> #include <queue> #include <cstdio> #include <algorithm> #include <cmath> using namespace std; #define NMAX 11111 int m,n; int minutes[NMAX]; int points[NMAX]; int dp[NMAX]; void debug_dummy() { return; } void test() { freopen("inflate.in","r",stdin); freopen("inflate.out","w",stdout); cin>>m>>n; for(int i=1;i<=n;i++) cin>>points[i]>>minutes[i]; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) for(int j=minutes[i];j<=m;j++) { dp[j]=max(dp[j],dp[j-minutes[i]]+points[i]); if (dp[j]>0)debug_dummy(); } cout<<dp[m]<<endl; } int main () { test(); return 0; }
test data:
USACO Training Grader Results 12 users online 61.10.110.236/1 CHN/3 DEU/2 IND/2 ROM/1 USA/2 YUG/1 USER: cn tom [qq104801] TASK: inflate LANG: C++ Compiling... Compile: OK Executing... Test 1: TEST OK [0.003 secs, 3500 KB] Test 2: TEST OK [0.005 secs, 3500 KB] Test 3: TEST OK [0.008 secs, 3500 KB] Test 4: TEST OK [0.008 secs, 3500 KB] Test 5: TEST OK [0.005 secs, 3500 KB] Test 6: TEST OK [0.014 secs, 3500 KB] Test 7: TEST OK [0.051 secs, 3500 KB] Test 8: TEST OK [0.111 secs, 3500 KB] Test 9: TEST OK [0.200 secs, 3500 KB] Test 10: TEST OK [0.211 secs, 3500 KB] Test 11: TEST OK [0.003 secs, 3500 KB] Test 12: TEST OK [0.003 secs, 3500 KB] All tests OK. YOUR PROGRAM ('inflate') WORKED FIRST TIME! That's fantastic -- and a rare thing. Please accept these special automated congratulations. Here are the test data inputs: ------- test 1 ---- 300 4 100 60 250 120 120 100 35 20 ------- test 2 ---- 10000 1 10000 1 ------- test 3 ---- 1000 20 40 11 333 336 2172 356 1958 537 9499 701 4443 275 6983 109 416 565 8155 166 7644 686 9596 828 4268 220 8396 953 8109 924 6048 452 5998 662 7201 550 4062 114 6713 122 4911 475 ------- test 4 ---- 4000 50 40 43 333 1341 2172 1423 1958 2148 9499 2802 4443 1100 6983 436 416 2258 8155 661 7644 2743 9596 3311 4268 878 8396 3811 8109 3693 6048 1805 5998 2647 7201 2197 4062 456 6713 486 4911 1900 3445 2257 2645 3475 4231 720 1637 2780 6455 2154 31 2494 2690 3149 3866 1845 5812 1508 2799 2414 8052 683 .............