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;
}

相關日誌