首页 > 代码库 > 【NOIP1999】邮票面值设计 dfs+dp
【NOIP1999】邮票面值设计 dfs+dp
题目传送门
这道题其实就是找一波上界比较麻烦 用一波 背包可以推出上界mx 所以新加入的物品价值一旦大于mx+1,显然就会出现断层,所以可以以maxm+1为枚举上界,然后这样进行下一层的dfs。
这样就愉快的解决问题了 23333
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int M=505; int read(){ int ans=0,f=1,c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘) f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){ans=ans*10+(c-‘0‘); c=getchar();} return ans*f; } int n,m,ans; int w[M],sum[M],f[M+7]; void dfs(int deep){ int mx; memset(f,0x3f,sizeof(f)); f[0]=0; for(mx=1;mx<=M;mx++){ for(int i=1;i<=deep&&w[i]<=mx;i++) f[mx]=min(f[mx],f[mx-w[i]]+1); if(f[mx]>n){ mx--; if(mx>ans){ ans=mx; for(int i=1;i<=deep;i++) sum[i]=w[i]; } break; } } if(deep==m) return ; for(int i=mx+1;i>w[deep];i--){ w[deep+1]=i; dfs(deep+1); } } int main() { n=read(); m=read(); w[1]=1; dfs(1); for(int i=1;i<=m;i++) printf("%d ",sum[i]); printf("\n"); printf("MAX=%d\n",ans); return 0; }
【NOIP1999】邮票面值设计 dfs+dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。