USACO 3.1.6 Stamps 邮票
不错的线性动态规划题，该题在NOIP2007提高组初赛试题中作为完善程序最后一题，不过是用搜索写的，对于这个题要用动态规划。
状态：设F[i]为组成面值为i所需要的最少的邮票数量 初始：F[0]=0 状态转移方程： F[i]=min{F[ i-value[j] ] (j=1..n and i-value[j]>=0) }+1 最终答案：找到最小的F[i]>k,则答案为(i-1)
解析：F[i]具有最有子策略，即F[i]由F[0..i-1]中特定的最优解决定。枚举每种邮票j，F[ i-value[j] ]为若F[i]中有邮票j，它就是不贴邮票j时，组成面值为i-value[j]所需要的邮票数量的最小值。为使F[i]为最优解，应取F[ i-value[j] ]构成的集合中的元素的最小值，并加1，表示选取了j这张邮票。
时间复杂度（最坏情况）：O(mnk) (m为每种邮票的面值最大值)
/*
ID: cmykrgb1
PROG: stamps
LANG: C++
*/
#include <stdio.h>
#define ITF 0x7FFFFFFF
FILE *fi,*fo;
long k,n;
long value[51];
long F[2000000];
inline long min(long a,long b)
{
return a<b?a:b;
}
int main()
{
long i,j,pmin;
fi=fopen("stamps.in","r");
fo=fopen("stamps.out","w");
fscanf(fi,"%ld%ld",&k,&n);
for (i=1;i<=n;i++)
fscanf(fi,"%ld",&value[i]);
F[i=0]=0;
while (F[i]<=k)
{
i++;pmin=ITF;
for (j=1;j<=n;j++)
if (i-value[j]>=0)
pmin=min(pmin,F[i-value[j]]);
F[i]=pmin+1;
}
fprintf(fo,"%ldn",i-1);
fclose(fi);
fclose(fo);
return 0;
}
上次修改时间 2017-02-03