uva 1377

比较不错的一个题,关键是理解状态转移

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 55
using namespace std;
int m,ans; int num[maxn],vis[maxn];
bool cnt[];
int scale[]; bool dfs(int cur)
{
// printf("%d %d\n",cur,ans);
if(cur==ans-)
{
for(int i=; i<m-; i++)
if(!vis[i])
return ;
return ;
} for(int i=; i<cur; i++)
{
for(int j=; j<m-; j++)
{
if(vis[j])continue;
int dd=scale[i]+num[j];
vis[j]=;
if(dd<=scale[cur-])continue;
if(dd>=num[m-])continue; scale[cur]=dd; queue<int>q;
while(!q.empty())q.pop(); for(int k=; k<cur; k++)
{
int tmp=dd-scale[k];
if(cnt[tmp]&&!vis[cnt[tmp]])
{
vis[cnt[tmp]]=;
q.push(cnt[tmp]);
}
} int tmp=num[m-]-scale[cur];
if(cnt[tmp]&&!vis[cnt[tmp]])
{
vis[cnt[tmp]]=;
q.push(cnt[tmp]);
} if(dfs(cur+))return ;
while(!q.empty())
{
vis[q.front()]=;
q.pop();
}
}
}
return ;
} int main()
{
int n,ca=;
while(scanf("%d",&n)&&n)
{
for(int i=; i<n; i++)
scanf("%d",&num[i]);
sort(num,num+n);
m=unique(num,num+n)-num; ans=;
while(ans*(ans-)/<m)
ans++;
memset(cnt,,sizeof cnt);
memset(vis,,sizeof vis);
for(int i=; i<m; i++)
cnt[num[i]]=i; scale[]=;
while(!dfs())
ans++;
scale[ans-]=num[m-];
printf("Case %d:\n",ca++);
printf("%d\n",ans); for(int i=;i<ans;i++)
printf("%d ",scale[i]);
puts("");
}
return ;
}
上一篇:Matlab绘图基础——colormap的使用


下一篇:OC可变參数的函数实现va_start、va_end、va_list的使用