USACO 3.1.6 Stamps（动态规划）解题报告

题目大意很简单，就是给出n中邮票的价值，求从 1 分开始连续的可用集合中不多于 K 张邮票贴出的邮资数。就是一个背包问题，

用dp[i]表示贴出价值为i的邮资所用的最少的邮票数，可得转移方程 dp[i]=max(dp[i-a[x]]+1,dp[i]) 其中a[x]为给出的n张邮票中的一种

最后，就顺序遍历dp数组，找出中断点。没什么难度

usaco 3.1.6 Stampsview raw

/*
ID:shiryuw1
PROG:stamps
LANG:C++
*/
#include <algorithm>
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

#define zero(a) memset(a,0,sizeof(a))
#define one(a) memset(a,1,sizeof(a))
#define fone(a) memset(a,-1,sizeof(a))
#define pow2(a) ((a)*(a))
#define pow3(a) ((pow2(a))*(a))

int dp[2000005];
int a[55];
int main()
{
	freopen("stamps.in","r",stdin);
	freopen("stamps.out","w",stdout);
	int k,n,i,j,maxn=-1;;
	scanf("%d%d",&k,&n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
		maxn=max(maxn,a[i]);
	}

	maxn*=k;
	for(i=1;i<=maxn;i++)
		dp[i]=(1<<25);
	dp[0]=0;
	for(i=0;i<n;i++)
	{
		for(j=a[i];j<=maxn;j++)
		{
			dp[j]=min(dp[j-a[i]]+1,dp[j]);
		}
	}

	for(i=1;i<=maxn;i++)
		if(dp[i]>k)
			break;
	printf("%d\n",i-1);
    return 0;
}