此题《算法艺术》上有详解。
最近做题果然不如以前，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 阅读(526)
评论(1) 编辑 收藏 引用 所属分类:
题目分类：递推/递归