luogu1510:精卫填海

#include<bits/stdc++.h>
using namespace std;
int f[30000000];
int a[10010];
int b[10010];
int main()
{
	int v,n,c,x=0,k=1;
	scanf("%d %d %d",&v,&n,&c);
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d",&a[i],&b[i]);
		
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=c;j>=b[i];j--)
		{
			f[j]=max(f[j],f[j-b[i]]+a[i]);
		}
	}
	while(f[k]<v)
	{
		k++;
		if(k>c)
		{
			printf("Impossible");
			return 0;
		}
	}
	printf("%d",c-k);
	return 0;
}
上一篇:【带权并查集 + DP】真正的骗子


下一篇:【CCPC2021 A】So Many Lucky Strings