题解 P1021 【邮票面值设计】

· · 题解

思路

动态规划，用f_{i}表示拼成i最少需要多少张邮票。 转移公式：f_j=min(f_j,f_{j-a_i}+1) 再来一个dfs就可以了。 （加上一个回溯）

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[21];
int maxx=0,ans[21];
int f[51000];
int dp(int k){
    memset(f,63,sizeof(f));//附一个较大的值
    f[0]=0;
    for(int i=1;i<=k;i++)
        for(int j=a[i];j<=a[k]*n;j++)
            if(f[j-a[i]]<n)
                f[j]=min(f[j],f[j-a[i]]+1);
    int x=0;
    while(f[x+1]<=100)
        x++;
    return x;
}
void dfs(int k){
    if(k==m+1){
        int t=dp(k-1);
        if(t>maxx){
            maxx=t;
            memcpy(ans,a,sizeof(ans));
        }
        return;
    }
    int end=dp(k-1);
    for(int j=a[k-1]+1;j<=end+1;j++){
        a[k]=j;
        dfs(k+1);
        a[k]=0;
    }
}
int main(){
    cin>>n>>m;
    a[1]=1;
    dfs(2);
    for(int i=1;i<=m;i++)
        printf("%d ",ans[i]);
    printf("\nMAX=%d\n",maxx);
    return 0;
}

谢谢--zhengjun