P1021 邮票面值设计

唔。。不早了我要睡觉了。。还要再发一篇我就不加解析了。。

搜索+深搜

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio>
 5 using namespace std;
 6 int n,k,res,ans[105],tmp[105],dp[2005];
 7 int calc(int dep,int sum)
 8 {
 9     memset(dp,0x3f,sizeof(dp));
10     dp[0]=0;
11     for(int i=1;i<=dep;i++)
12         for(int j=tmp[i];j<=n*sum;j++)
13             dp[j]=min(dp[j],dp[j-tmp[i]]+1);
14     for(int i=1;i<=n*sum;i++)
15         if(dp[i]>n)
16             return i-1;
17     return n*sum;
18 }
19 void dfs(int dep,int lst1,int lst2,int sum)
20 {
21     if(dep>k)
22     {
23         if(res<lst2)
24         {
25             res=lst2;
26             for(int i=1;i<=k;i++)
27                 ans[i]=tmp[i];
28         }
29         return ;
30     }
31     for(int i=lst1+1;i<=lst2+1;i++)
32     {
33         tmp[dep]=i;
34         int x=calc(dep,sum+i);
35         dfs(dep+1,i,x,sum+i);
36     }
37 }
38 int main()
39 {
40     scanf("%d%d",&n,&k);
41     dfs(1,0,0,0);
42     for(int i=1;i<=k;i++)
43         printf("%d ",ans[i]);
44     printf("
MAX=%d
",res);
45     return 0;
46 }