首页 > 代码库 > 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;}
View Code