传送门
//题意: 给定n个数和一个位置k, 定义F(n) 为题目中的要求. 问必须移动这n个元素中的某一个数恰好k位(往前或往后), 问怎样移动是的F(n)的值最大. 给出的n个数以非递减的顺序给出.
//思路: 非递减的顺序很重要, 这样的话一定是移动某一个数往前移是最优的. 具体证明就不给出了. 其实仔细想想就可以明白. 然后有了这个前提, 我们就可以枚举每一个数往前移动k为时可以得到的答案, 然后输出最大值就行了. 然后就是如何快速得到某一段的值了. 这时就需要前缀的思想了. 具体实现请看代码. AC Code const int maxn = 1e5+5; ll tt[maxn]; ll a[maxn],b[maxn]; void solve() { Fill(a,0); Fill(b,0); int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;i++){ scanf("%lld",&tt[i]); a[i] = a[i-1] + tt[i]*i; b[i] = b[i-1] + tt[i]*(i+1); //因为最多向前移动一位,所以求一下前缀. } ll res = b[k] + tt[k+1] + a[n] - a[k+1]; for(ll i=k+2;i<=n;i++){ ll m = i-k; ll tmp = b[i-1] - b[m-1] + a[m-1] + a[n] - a[i] + 1ll*m*tt[i]; res = max(tmp,res); //写这一步的时候思路一定要清楚!!!就是个前缀. } printf("%lld ",res); }