小目录

• • 题目描述
  • 样例输入
  • 样例输出
  • 思路
  • 代码

题目描述

给出n个位置，m种人，每个人有个价值a[i],现在这n个位置，最多可以放n个人，放完人后能得到一个价值v[i]，现在求一个MAX，1~MAX的每一个价值都能放置出

样例输入

4    
2
1
4

样例输出

10

思路

设 f i f_i fi​为凑出价值i所需要的最小人数，则
f j = m i n ( f j − x i + 1 , f j ) f_j = min(f_{j- x_i} + 1, f_j) fj​=min(fj−xi​​+1,fj​)

代码

#include<algorithm>
#include<iostream>
#include<cstring> 
#include<cstdio>

using namespace std;

int f[30005], x[105], n, m;

int main()
{
	freopen("stamps.in", "r", stdin);
	freopen("stamps.out", "w", stdout);
	memset(f, 0x7f, sizeof(f));
	scanf("%d", &n);
	scanf("%d", &m);
	for(int i = 1; i <= m; ++i)
		scanf("%d", &x[i]);
	f[0] = 0;
	for(int i = 1; i <= m; ++i)
		for(int j = x[i]; j <= 30000; ++j)
			if(f[j - x[i]] < n) 
				f[j] = min(f[j - x[i]] + 1, f[j]);
	for(int i = 1; i <= 30000; ++i)
		if(f[i] > n)
		{
			printf("%d", i - 1);
			return 0;
		}
	return 0;
}