題解參見《算法藝術(shù)與信息學(xué)競賽》。
以下是我的代碼：
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int kInf(0x7f7f7f7f);
int main()
{
#ifndef ONLINE_JUDGE
freopen("data.in","r",stdin);
#endif
int n,m,r[315],a[15];
int t[315];
bool found;
while(scanf("%d",&n)==1)
{
m=n*(n-1)/2;
for(int i=1;i<=m;i++)
scanf("%d",&r[i]);
sort(r+1,r+m+1);
found=false;
for(int p=3;p<=m && !found;p++)
{
bool impossible(false);
for(int i=1;i<=n;i++)
a[i]=-kInf;
memcpy(t,r,sizeof(t));
if((t[1]-t[2]+t[p])%2)
continue;
a[2]=((t[1]-t[2]+t[p])/2);
a[1]=t[1]-a[2];
a[3]=t[p]-a[2];
t[1]=t[2]=t[p]=kInf;
for(int i=4;i<=n;i++)
{
int minv(kInf);
for(int j=1;j<=m;j++)
minv=min(minv,t[j]);
if(minv==kInf)
{
impossible=true;
break;
}
a[i]=minv-a[1];
for(int j=1;j<i;j++)
if(a[j]!=-kInf)
{
int pos(-1);
for(int k=1;k<=m;k++)
if(t[k]==a[i]+a[j])
{
pos=k;
break;
}
if(pos==-1)
{
impossible=true;
break;
}
t[pos]=kInf;
}
if(impossible)
break;
}
if(!impossible)
found=true;
}
if(!found)
{
printf("Impossible\n");
continue;
}
for(int i=1;i<=n;i++)
{
if(i!=1)
printf(" ");
printf("%d",a[i]);
}
printf("\n");
}
return 0;
}
posted on 2011-08-30 10:51
lee1r 閱讀(678)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
題目分類：遞推/遞歸