USACO 3.1.6 Stamps 郵票
本文正體字版由OpenCC轉換
不錯的線性動態規劃題，該題在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