这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
呼呼,先背题目给骗了,看了刘如佳老师的《算法艺术》那本书里,在讲递推时给出了这个例题,看到方法有点麻烦,时间复杂度是O(n^3),碰巧在HDOJ上找到了这题,无奈下不了手。。。
结果和论坛的朋友一讨论,才发现自己被这题骗了,按照看清题目后的感觉来说,这题就是水题了~~~呼呼。
为什么呢?因为他输入给出的就是先把a1从a2一直加到an,然后在a2从a3一直加到an,等于顺序已经搞定,前几个数都确定了。。。就这样~~~~水过。
代码:
// Author: Tanky Woo
// HDOJ 2515
//Accepted 2515 0MS 212K 572B C++ Tanky Woo
#include
using namespace std;
// www.wutianqi.com
int result[1300];
int yanghee[55];
int main()
{
//freopen("input.txt", "r", stdin);
int n, num;
scanf("%d", &n;);
num = n*(n-1)/2;
for(int i = 1; i <= num; ++i)
scanf("%d", &result;[i]);
// A1+A2=R1, A1+A3=R2,A2+A3=Rn
// A2 = (R1-R2+Rn)/2
yanghee[2] = (result[1]-result[2]+result[n])/2;
yanghee[1] = result[1]-yanghee[2];
for(int i = 2; i <= n-1; ++i)
yanghee[i+1] = result[i]-yanghee[1];
for(int i = 1; i <= n; ++i)
printf("%d\n", yanghee[i]);
return 0;
}