Beyond the Void
BYVoid
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

相关日志