【NOIP1999】邮票面值设计 dfs+dp

题目传送门

这道题其实就是找一波上界比较麻烦 用一波 背包可以推出上界mx 所以新加入的物品价值一旦大于mx+1,显然就会出现断层,所以可以以maxm+1为枚举上界,然后这样进行下一层的dfs。

这样就愉快的解决问题了 23333

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=;
int read(){
int ans=,f=,c=getchar();
while(c<''||c>''){if(c=='-') f=-; c=getchar();}
while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}
return ans*f;
}
int n,m,ans;
int w[M],sum[M],f[M+];
void dfs(int deep){
int mx;
memset(f,0x3f,sizeof(f));
f[]=;
for(mx=;mx<=M;mx++){
for(int i=;i<=deep&&w[i]<=mx;i++) f[mx]=min(f[mx],f[mx-w[i]]+);
if(f[mx]>n){
mx--;
if(mx>ans){
ans=mx;
for(int i=;i<=deep;i++) sum[i]=w[i];
}
break;
}
}
if(deep==m) return ;
for(int i=mx+;i>w[deep];i--){
w[deep+]=i;
dfs(deep+);
}
}
int main()
{
n=read(); m=read();
w[]=;
dfs();
for(int i=;i<=m;i++) printf("%d ",sum[i]);
printf("\n");
printf("MAX=%d\n",ans);
return ;
}
上一篇:【原】Redis-LRU缓存


下一篇:ComboBox的联动