SP8284 WEIGHT - Weighted Sum
题意描述
给出长度为n(n<=1e6)的序列A， A中元素可能为正数，可为负数或0，。让你构造一个长度为n的序列W，给这些整数A赋权，使它们的加权和最大化。权重W应满足以下条件：
-
每个权重都应该是一个正整数。(W中每个元素都是正数)
-
W[1]=1
-
对于i>1，W[i]应在范围[2，W[i-1]+1]内。(
W[i] ∈[2,W[i-1]+1] (i>1))
让你构造一个满足这样条件的序列W， 使得ΣA[i]×W[i]最大
输入格式
有多组数据。
第一行数据组数
每组数据第一行为n，后面是n行，每行一个A[i]
输出格式
对于每组数据，输出一行最大加权和；
输入样例
1
4
1
2
3
-4
输出样例
6
翻译：So_what
分析（by Chelly）
简单地分析下W数组的性质
对于那些负数A[i]， 为了让总和最大， 我们肯定希望W[i]越小越好， 2是最好的。
对于连续的一串正数A[l..r]， 我们肯定希望W[l..r]越大越好， 那么肯定是依次是2 3 4 5 6 ... r-l+2
那么是不是对于每个负数A[i]， 对应的W[i]就是2； 对应连续的一串正数， W[i]就是2 3 4 5.....这样呢？
看这样的例子： A[4]={-1,-2,2,10000} 那么W[4]={2,3,4,5}比W[4]={2,2,3,4}更优
我们考虑一串A[l..r]， 假设目前的W是2 3 4 5 6....
那么现在的问题的就是对于前面一个A[l-1]， 我们究竟要不要将2从W[l-1]开始， 后面的W[l..r]改成3 4 5 6....
注意到如果这样更改， 那么实际上[l,r]对总结果的贡献改变了sum[l..r]
我们肯定希望改变值sum[l..r]是正的
从A序列尾部r向前扫描， 直到扫到一个位置l， sum[l..r]<0， 那么这段位置的W值就依次是2 3 4 5 6 7 ....
将l-1作为新的r往前继续扫描， 直到扫描完整个A序列
为了满足时间复杂度， 需要高效地统计答案
往前扫的过程中， 我们可以假定当前位置是2， 得到目前的ans， 然后如果判定可以向前移动一位， 那么相当于这些位置的W都对应加1， 对于总的结果来说， 就是加上这一段的sum
时间复杂度O(n)
#include<cstdio>
using namespace std;
int T,n,a[1000005];
int main() {
scanf("%d",&T);
while(T--) {
scanf("%d",&n);
for (int i=1; i<=n; i++) scanf("%d",&a[i]);
long long ans=0,s=0,sum=0;//ans最大权值和，s当前段的最大权值和，sum当前段的A[]后缀和
for (int i=n; i; i--) {
sum+=a[i];
s+=sum+a[i];//给s+=sum相当于把sum中每个数增加一倍（权值和为正），每个A至少×2，所以s加上两次a[i]
if (sum<0 || i==1) {
if (i==1) s-=sum;//W[1]=1
ans+=s,s=sum=0;//若后缀和变为0，则w[i]取最小2，sum清零
}
}
printf("%lld
",ans);
}
return 0;
}