STAMPS

POJ 1010

只用于记录

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;int go[33];
int d[5],ans[5];
int n;
int len,real_len;
bool isequal;
int cur;int num(int deep)
{bool vis[33];memset(vis,false,sizeof(vis));int x=0;for (int i=0;i<deep;i++) if (!vis[d[i]]){vis[d[i]]=true;x++;}//for (int i=0;i<deep;i++) cout<<d[i]<<' ';cout<<x<<endl;return x;
}void cmp(int deep)
{int i;int x=num(deep);//cout<<(x==len)<<' '<<(deep==real_len)<<' '<<(d[0]==ans[0])<<endl;// {for (int i=0;i<deep;i++) cout<<go[d[i]]<<' ';cout<<endl;}// cout<<go[d[0]]<<' '<<go[ans[0]]<<endl;if (x>len){len=x;real_len=deep;for (i=0;i<deep;i++) ans[i]=d[i];isequal=false;}else if (x==len){if (deep<real_len){real_len=deep;for (i=0;i<deep;i++) ans[i]=d[i];isequal=false;}else if (deep==real_len){if (go[d[0]]>go[ans[0]])  //这里要注意要加go，ans[],d[]只是go的索引值 {for (i=0;i<deep;i++) ans[i]=d[i];isequal=false;}else if (go[d[0]]==go[ans[0]]) isequal=true;}}}void cmp2(int deep)
{int x=num(deep);cout<<x<<endl;if (len==0 || x>len || (x==len&&real_len>deep) || (x==len&&real_len==deep&&d[0]>ans[0])){len=x;real_len=deep;for (int i=0;i<deep;i++) ans[i]=d[i];isequal=false;}if (x==len&&real_len==deep&&d[0]==ans[0]) isequal=true;
}void dfs(int p,int sum,int deep)
{if (sum == cur){//for (int i=0;i<deep;i++) cout<<go[d[i]]<<' ';cout<<endl;cmp(deep);return;	}if (deep==4) return ;for (int i=p;i<n;i++) if (sum+go[i]<=cur){d[deep]=i;dfs(i,sum+go[i],deep+1);}
}bool comp(int a,int b)
{return a>b;
}int main()
{freopen("in","r",stdin);int i,j,k;while (cin>>go[0]){n=1;if (go[0])while (cin>>go[n]){if (go[n]) n++;else break;}sort(go,go+n,comp);while (cin>>cur,cur){len=0;real_len=0;isequal=false;dfs(0,0,0);printf("%d ",cur);if (len==0) printf("---- none\n");else if (isequal) printf("(%d): tie\n",len);else {printf("(%d):",len);for (i=real_len-1;i>=0;i--) printf(" %d",go[ans[i]]);printf("\n");}}}}

STAMPS

POJ 1010

只用于记录

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;int go[33];
int d[5],ans[5];
int n;
int len,real_len;
bool isequal;
int cur;int num(int deep)
{bool vis[33];memset(vis,false,sizeof(vis));int x=0;for (int i=0;i<deep;i++) if (!vis[d[i]]){vis[d[i]]=true;x++;}//for (int i=0;i<deep;i++) cout<<d[i]<<' ';cout<<x<<endl;return x;
}void cmp(int deep)
{int i;int x=num(deep);//cout<<(x==len)<<' '<<(deep==real_len)<<' '<<(d[0]==ans[0])<<endl;// {for (int i=0;i<deep;i++) cout<<go[d[i]]<<' ';cout<<endl;}// cout<<go[d[0]]<<' '<<go[ans[0]]<<endl;if (x>len){len=x;real_len=deep;for (i=0;i<deep;i++) ans[i]=d[i];isequal=false;}else if (x==len){if (deep<real_len){real_len=deep;for (i=0;i<deep;i++) ans[i]=d[i];isequal=false;}else if (deep==real_len){if (go[d[0]]>go[ans[0]])  //这里要注意要加go，ans[],d[]只是go的索引值 {for (i=0;i<deep;i++) ans[i]=d[i];isequal=false;}else if (go[d[0]]==go[ans[0]]) isequal=true;}}}void cmp2(int deep)
{int x=num(deep);cout<<x<<endl;if (len==0 || x>len || (x==len&&real_len>deep) || (x==len&&real_len==deep&&d[0]>ans[0])){len=x;real_len=deep;for (int i=0;i<deep;i++) ans[i]=d[i];isequal=false;}if (x==len&&real_len==deep&&d[0]==ans[0]) isequal=true;
}void dfs(int p,int sum,int deep)
{if (sum == cur){//for (int i=0;i<deep;i++) cout<<go[d[i]]<<' ';cout<<endl;cmp(deep);return;	}if (deep==4) return ;for (int i=p;i<n;i++) if (sum+go[i]<=cur){d[deep]=i;dfs(i,sum+go[i],deep+1);}
}bool comp(int a,int b)
{return a>b;
}int main()
{freopen("in","r",stdin);int i,j,k;while (cin>>go[0]){n=1;if (go[0])while (cin>>go[n]){if (go[n]) n++;else break;}sort(go,go+n,comp);while (cin>>cur,cur){len=0;real_len=0;isequal=false;dfs(0,0,0);printf("%d ",cur);if (len==0) printf("---- none\n");else if (isequal) printf("(%d): tie\n",len);else {printf("(%d):",len);for (i=real_len-1;i>=0;i--) printf(" %d",go[ans[i]]);printf("\n");}}}}