[NOIP1999提高] CODEVS 1047 邮票面值设计(dfs+dp)

[NOIP1999提高] CODEVS 1047 邮票面值设计(dfs+dp)

dfs出邮票的各种面值,然后dp求解。

-------------------------------------------------------------------------------

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
 
#define rep(i,n) for(int i=0;i<n;++i) 
#define clr(x,c) memset(x,c,sizeof(x))
#define Rep(i,l,r) for(int i=l;i<=r;++i)
 
using namespace std;
 
const int maxn=40;
const int inf=5000000;
 
vector<int> ans;
int cur[maxn];
int ANS=0;
int ok[4000000];
int n,k;
int t=0;
 
void jud() {
int a=0; ok[0]=0;
while(ok[a]<=n) {
ok[++a]=inf;
   rep(i,k) {
    if(a<cur[i]) break;
    ok[a]=min(ok[a],ok[a-cur[i]]+1);
   }
}
if(--a>ANS) {
ANS=a;
ans.clear();
rep(i,k) ans.push_back(cur[i]);
}
}
 
void dfs(int x) {
if(x==k) jud();
else Rep(i,cur[x-1]+1,cur[x-1]*n+1) {
   cur[x]=i;
dfs(x+1);
}
}
int main()
{
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);
scanf("%d%d",&n,&k);
dfs(cur[0]=1);
rep(i,ans.size()) printf("%d ",ans[i]);
printf("\nMAX=%d\n",ANS);
return 0;
}

-------------------------------------------------------------------------------

1047 邮票面值设计

1999年NOIP全国联赛提高组

 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 钻石 Diamond
上一篇:Jquery基础(动画效果的轮播图特效)


下一篇:P1021 邮票面值设计