题解 P1021 【邮票面值设计】

· · 题解

我的博客：

https://blog.csdn.net/zsyzClb/article/details/84143699

这一道题不难想出用搜索做，通过枚举枚举出所有种类的邮票，最后判断一下，并记录最大值

但是，直接暴力搜索肯定会超时的，所以我用了以下几个剪枝优化：

（在这里我用a数组记录搜索的值）

剪枝1:我们可以使a数组保持单调递增，dfs中每次从a[k-1]+1开始搜索，以此来消除重复的搜索

剪枝2:我们通过看题，可以知道1肯定会被选用，不然怎么组成1的，所以我们使a[1]=1，然后从第2项开始搜索（这个剪枝意义不大，不过个人喜欢）

 

剪枝3:这个剪枝可以说是这一道题的难点，

如何判断每次dfs枚举的上界!!!!!!

（每次从a[k-1]+1到50是肯定会超时的）

假设当前准备填第k个（已经填好了k-1）个

所以在前k-1个中可以凑出1-t中的所有整数（需要用dp求出t）

因此我们可以把上界定为t+1

t+1，不是t，自己想想为什么？

如果超过了t+1，那么就无法组成t+1了。

所以dfs搜索的范围是

for(int i=a[k-1]+1;i<=t+1;i++)

对了，刚才不是说要用dp吗，那么怎么dp？

dp[i]表示对于当前的a数组组成i所需要最小的个数

所以dp[i]=min(dp[i],dp[i-a[i]]+1)，初始化+oo，dp[0]=0

代码（你们最想要的)：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
using namespace std;
int n,m;
int a[21];//暂时的储存 
int maxx=0,ans[21];//ans和maxx记录最终结果 
int dp[51000];//dp数组 
int solve(int k){
    memset(dp,63,sizeof(dp));dp[0]=0;
    for(int i=1;i<=k;i++)//前k个数 
        for(int j=a[i];j<=a[k]*n;j++)//最多能组成到a[k]*n，表示全部都选最大的数 
            if(dp[j-a[i]]<n)//只能继承的<n 
                dp[j]=min(dp[j],dp[j-a[i]]+1);//当然是求最小值，以后才可以用 
    int x=0;
    while(dp[x+1]<=100)x++;//得到最长的连续前缀 
    return x;
}
void dfs(int k){
    if(k==m+1){//如果找到m个 
        int t=solve(k-1);
        if(t>maxx){
            maxx=t;
            memcpy(ans,a,sizeof(ans));
        }
        return;
    }
    int end=solve(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;//把n,k改变为n,m 
    a[1]=1;//剪枝2 
    dfs(2);//从第2个开始问 
    for(int i=1;i<=m;i++)printf("%d ",ans[i]);//输出 
    printf("\nMAX=%d\n",maxx);
    return 0;
}