此題《算法藝術》上有詳解。
最近做題果然不如以前，WA了幾次……
WA的原因如下：
1、a[i]+a[j]寫成a[1]+a[j]；
2、注意從原序列中刪除x的時候，序列中可能存在多個x，此時只能刪除1次，不能重復刪除；甚至有可能x不存在，這說明當前枚舉的a[2]+a[3]的值不符合要求。
以下是我代碼：
#include<iostream>
#include<string.h>
#define maxn 57
#define INF 200007
using namespace std;
long n,a[maxn],r[maxn*maxn/2];
long m,t[maxn*maxn/2];
bool okay,impossible;
long pos(long x)
{
for(long i=1;i<=n*(n-1)/2;i++)
if(t[i]==x) return i;
return -1;
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
cin>>n;
for(long i=1;i<=n*(n-1)/2;i++)
cin>>r[i];
// Input
okay=false;
for(long p=3;p<=n*(n-1)/2&&r[p]<r[1]+r[2]&&!okay;p++)
{
memset(a,0,sizeof(a));
for(long i=1;i<=n*(n-1)/2;i++)
t[i]=r[i];
if((t[1]+t[2]-t[p])%2!=0) continue;
a[1]=(t[1]+t[2]-t[p])/2;
a[2]=(t[1]-t[2]+t[p])/2;
a[3]=(t[2]+t[p]-t[1])/2;
if(a[1]<=0||a[2]<=0||a[3]<=0) continue;
t[1]=t[2]=t[p]=INF;
for(long i=4;i<=n;i++)
{
m=INF;
for(long j=1;j<=n*(n-1)/2;j++)
if(t[j]<m) m=t[j];
// Find min_num
a[i]=m-a[1];
if(a[i]<=0) break;
impossible=false;
for(long j=1;j<=i-1;j++)
{
long tmp=pos(a[i]+a[j]);
if(tmp<0)
{
impossible=true;break;
}
t[tmp]=INF;
}
// Delete
if(impossible) break;
if(i==n) okay=true;
}
}
for(long i=1;i<=n;i++)
cout<<a[i]<<endl;
// Output
return 0;
}
posted on 2010-07-09 11:05
lee1r 閱讀(568)
評論(1) 編輯 收藏 引用 所屬分類:
題目分類：遞推/遞歸