郵票面值設計（NOIP1999）

傳送門

怎麼講呢？

挺有意思的

是一道dp和搜尋的結合。

我們把數字從小到大依次枚舉。

用dp去計算目前的所得最大值。

f[i]表示湊成i面值所需的最小郵票數量。

那麼小于等于n的，都是可以湊出來的。

那麼最大值也就好求了。

至于dp的上界，用幾個數的和就能解決。

代碼如下：

#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
int n,k,res,ans[],curans[],f[];
int solve(int dep,int sum){
    memset(f,,sizeof(f));
    f[]=;
    for(int i=;i<=dep;i++){
        for(int j=curans[i];j<=n*sum;j++){
            f[j]=min(f[j],f[j-curans[i]]+);
        }
    }
    for(int i=;i<=n*sum;i++){
        if(f[i]>n){
            return i-;
        } 

    } 
    return n*sum;
}
void dfs(int dep,int last,int maxn,int sum){
    if(dep>k){
        if(res<maxn){
            res=maxn;
            for(int i=;i<=k;i++){
                ans[i]=curans[i];
            } 
        }
        return;
    }
    for(int i=last+;i<=maxn+;i++){
        curans[dep]=i;
        int x=solve(dep,sum+i);
        dfs(dep+,i,x,sum+i);
    }
}
int main(){
    scanf("%d%d",&n,&k);
    dfs(,,,);
    for(int i=;i<=k;i++){
        printf("%d ",ans[i]);
    }
    printf("\nMAX=%d\n",res);
    return ;
}