游客 注册 | 登录
中文 | En

2206 - 捡贝壳

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

    萩萩萩是个爱收藏的孩子，他特别喜欢贝壳。有一天，他去到海边，看到有好多好多的贝壳。于是他在时间t内拣了价值为v的贝壳.

题目输入

    第一行有两个整数 T(1 <= T <= 1000) 和M(1<= M <= 100),用一个空格隔开,T代表总共能够用来


捡贝壳的时间，M代表贝壳的数目。接下来M行包括两个在1到100之间（包括1和100）的整数，分别表

示捡这个贝壳的时间和这个贝壳的价值。

题目输出

输出包括一行，这一行知包含一个整数，表示在规定的时间内，可以捡到的贝壳的最大价值。

输入/输出样例

输入格式

70 3
71 100
69 1
1 2

输出格式

3

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;
}

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]);
  }
}
请先登陆