icpc2018焦作-I. Distance

约定不等于承诺〃 2021-12-23 11:07 198阅读 0赞

第一发又超时了。。。

题目大意：给你n个点，然后给你n-1的数，表示两两距离，然后让你输出n个答案，第i个答案表示从这n个点里面挑i个点，然后这i个点两两之间会有一个距离，答案要求这些距离和的最大值。

第一次思路：n个点，给你距离，我们可以得到在坐标轴上表示n个点的坐标，然后我们可以先设每个点坐标为xi

可以发现：当n>=2的时候

n=2,i=2 距离为x2-x1

n=3,i=2距离为x3-x1 i=3距离为 x2-x1+x3-x1+x3-x2=2\*x3-2\*x1

n=5,i=2距离为x5-x1,i=5距离为4\*x5-4\*x1+2\*x4-2\*x3

以此类推我发现了对于每种情况下当n固定时比如n是5。i从2开始，i为2答案为（i-1）\*两边第一个数之差，i=3时，答案为（i-1）\*两边第一个数之差,i为4时，答案为(i-1)\*第一个数之差+(i-3)\*第二个数之差。至此找到规律。n固定时，第i个答案为(i-1)\*两边第一个数之差+(i-3)\*两边第二个数之差+（i-5）\*两边第三个数之差......

这样一直加到i-x这个数<=0停止。于是就敲出了代码但超时了。。。

思路重新梳理，可以发现对于每种i之间是有联系的，对于每个i是前一个i的答案的基础上多加了两边之差的前（i/2）项的前缀和。

表述难以表达清楚，还是得好好推推想想。

#include<bits/stdc++.h>
    using namespace std; const int maxn=1e5+10; long long a[maxn]; long long c[maxn]; long long sum[maxn]; int main() { ios::sync_with_stdio(false); cin.tie(0); int t; cin>>t; while(t--) { int n; cin>>n; memset(a,0,sizeof(a)); memset(sum,0,sizeof(sum)); memset(c,0,sizeof(c)); a[1]=1; for(int i=1; i<=n-1; i++) { int d; cin>>d; a[i+1]=a[i]+d; } for(int i=1; i<=n/2; i++) c[i]=a[n+1-i]-a[i]; for(int i=1; i<=n/2; i++) sum[i]=sum[i-1]+c[i]; printf("0"); long long tt=0; int cnt=1; for(int i=2; i<=n; i++) { tt=tt+sum[i/2]; printf(" %lld",tt); } printf("\n"); } }

转载于:https://www.cnblogs.com/dongdong25800/p/10701488.html