2206 - 捡贝壳
萩萩萩是个爱收藏的孩子，他特别喜欢贝壳。有一天，他去到海边，看到有好多好多的贝壳。于是他在时间t内拣了价值为v的贝壳.
Input
第一行有两个整数 T(1 <= T <= 1000) 和M(1<= M <= 100),用一个空格隔开,T代表总共能够用来
捡贝壳的时间，M代表贝壳的数目。接下来M行包括两个在1到100之间（包括1和100）的整数，分别表
示捡这个贝壳的时间和这个贝壳的价值。
Output
输出包括一行，这一行知包含一个整数，表示在规定的时间内，可以捡到的贝壳的最大价值。
Examples
Input
70 3 71 100 69 1 1 2
Output
3
Solution C
#include <stdio.h> #include <string.h> int main() { int T, M, result[1024], time, price, i; while (EOF != scanf("%d%d", &T, &M)){ memset(result, 0, sizeof(result)); while (M--){ scanf("%d%d", &time, &price); if (time > T){ continue; } for (i = T; i >= time; i--){ if (result[i-time]+price > result[i]){ result[i] = result[i-time]+price; }else{ result[i] = result[i]; } } } printf("%d\n", result[T]); } return 0; }
Solution C++
#include <stdio.h> #include <algorithm> #include <cstring> using namespace std; const int V = 100 + 50; int t, n, dp[V]; int main() { while(~scanf("%d%d", &t, &n)) { memset(dp, 0, sizeof(dp)); while(n--) { int a, b; scanf("%d%d", &a, &b); for(int j = t; j >= a; --j) dp[j] = max(dp[j], dp[j - a] + b); } printf("%d\n", dp[t]); } }