P1021 邮票面值设计

题目描述

给定一个信封，最多只允许粘贴n张邮票，计算在给定k（n+k≤15）种邮票的情况下（假定所有的邮票数量都足够），如何设计邮票的面值，能得到最大值max，使在1至max之间的每一个邮资值都能得到。

例如，n=3，k=2，如果面值分别为1分、4分，则在1分～6分之间的每一个邮资值都能得到（当然还有8分、9分和12分）；如果面值分别为1分、3分，则在1分～7分之间的每一个邮资值都能得到。可以验证当n=3，k=2时，7分就是可以得到的连续的邮资最大值，所以max=7，面值分别为1分、3分。

输入格式

2个整数，代表n，k。

输出格式

2行。第一行若干个数字，表示选择的面值，从小到大排序。

第二行，输出“max=s”，s表示最大的面值。

输入输出样例

输入 #1复制

3 2

输出 #1复制

1 3
max=7

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
int a[201],ans[201],dp[50001];
int n,k,maxx=0;
int sol(int m){
    int i,j;
    memset(dp,0x3f3f3f,sizeof(dp));
    dp[0]=0;
    for(i=1;i<=m;i++){
        for(j=a[i];j<=a[m]*n;j++){
            if(dp[j-a[i]]<n){
                dp[j]=min(dp[j],dp[j-a[i]]+1);
            }
        }
    }
    int sum=0;
    while(dp[sum+1]<=100){
        sum++;
    }
    return sum;
}
void dfs(int m){
    if(m==k+1){
        int t=sol(m-1);
        if(t>maxx){
            maxx=t;
            memcpy(ans,a,sizeof(ans));
        }
        return ;
    }
    int t=sol(m-1);
    for(int i=a[m-1]+1;i<=t+1;i++){
        a[m]=i,dfs(m+1),a[m]=0;
    }
}
int main(){
    scanf("%d%d",&n,&k);
    a[1]=1;
    dfs(2);
    for(int i=1;i<=k;i++){
        printf("%d ",ans[i]);
    }
    printf("\nmax=%d\n",maxx);
    return 0;
}