【数据结构】guard
部队中共有N个士兵，每个士兵有各自的能力指数Xi，在一次演练中，指挥部确定了M个需要防守的地点，按重要程度从低到高排序，依次以数字1到M标注每个地点的重要程度，指挥部将选择M个士兵依次进入指定地点进行防守，能力指数为X的士兵防守重要程度为Y的地点将得到X*Y的参考指数。选择出连续的M个士兵依次参加防守，使得总的参考指数值最大。
输入格式：输入第一行有两个整数N,M(1<=N<=1000000，1<=M<=1000)；第二行N个整数表示每个士兵对应的能力指数Xi（1<=Xi<=1000）
输出格式：输出一个整数，为最大的参考指数总和。
输入示例：5 3 \n 2 1 3 1 4
输出示例：17（31+12+4*3=17）
#include <stdio.h>
#define N 1000005
int qzh[N],qzhdqzh[N]; //qzh前缀和，qzhdqzh前缀和的前缀和
int main(){
qzh[0]=qzhdqzh[0]=0;
int n,m;scanf("%d%d",&n,&m);
int ability;
for(int i=1;i<=n;i++){ //i=1，第一个士兵
scanf("%d",&ability);
qzh[i]=qzh[i-1]+ability; //计算前缀和
qzhdqzh[i]=qzhdqzh[i-1]+qzh[i]; //计算前缀和的前缀和
}
int max,t=0;
for(int i=m;i<=n;i++){ //i=m表示窗口为第一个到第m个士兵
max=m*qzh[i]-(qzhdqzh[i-1]-qzhdqzh[i-1-m]); //计算每个窗口总参考指数
if(max>t)t=max;
}
printf("%d",t);
return 0;
}