首页 > 代码库 > uva 1377
uva 1377
比较不错的一个题,关键是理解状态转移
#include<algorithm>#include<cstdio>#include<cstring>#include<queue>#define maxn 55using namespace std;int m,ans;int num[maxn],vis[maxn];bool cnt[1000009];int scale[10];bool dfs(int cur){// printf("%d %d\n",cur,ans); if(cur==ans-1) { for(int i=0; i<m-1; i++) if(!vis[i]) return 0; return 1; } for(int i=0; i<cur; i++) { for(int j=0; j<m-1; j++) { if(vis[j])continue; int dd=scale[i]+num[j]; vis[j]=1; if(dd<=scale[cur-1])continue; if(dd>=num[m-1])continue; scale[cur]=dd; queue<int>q; while(!q.empty())q.pop(); for(int k=0; k<cur; k++) { int tmp=dd-scale[k]; if(cnt[tmp]&&!vis[cnt[tmp]]) { vis[cnt[tmp]]=1; q.push(cnt[tmp]); } } int tmp=num[m-1]-scale[cur]; if(cnt[tmp]&&!vis[cnt[tmp]]) { vis[cnt[tmp]]=1; q.push(cnt[tmp]); } if(dfs(cur+1))return 1; while(!q.empty()) { vis[q.front()]=0; q.pop(); } } } return 0;}int main(){ int n,ca=1; while(scanf("%d",&n)&&n) { for(int i=0; i<n; i++) scanf("%d",&num[i]); sort(num,num+n); m=unique(num,num+n)-num; ans=2; while(ans*(ans-1)/2<m) ans++; memset(cnt,0,sizeof cnt); memset(vis,0,sizeof vis); for(int i=0; i<m; i++) cnt[num[i]]=i; scale[0]=0; while(!dfs(1)) ans++; scale[ans-1]=num[m-1]; printf("Case %d:\n",ca++); printf("%d\n",ans); for(int i=0;i<ans;i++) printf("%d ",scale[i]); puts(""); } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。