http://acm.fzu.edu.cn/problem.php?pid=2168
Description
部队中共有N个士兵，每个士兵有各自的能力指数Xi，
在一次演练中，指挥部确定了M个需要防守的地点，按重要程度从低到高排序，
依次以数字1到M标注每个地点的重要程度，
指挥部将选择M个士兵依次进入指定地点进行防守任务，
能力指数为X的士兵防守重要程度为Y的地点将得到X*Y的参考指数。
现在士兵们排成一排，请你选择出连续的M个士兵依次参加防守,使得总的参考指数值最大。
Input
输入包含多组数据。
输入第一行有两个整数N,M(1<=N<=1000000，1<=M<=1000),
第二行N个整数表示每个士兵对应的能力指数Xi（1<=Xi<=1000）。
对于30%的数据1<=M<=N<=1000。
Output
输出一个整数，为最大的参考指数总和。
Sample Input
5 3
2 1 3 1 4
Sample Output
17
思路：
直接暴力必然超时
但是每m个数字的序列和 可以通过递推公式
s=s-m*a[i+1]+sum[i];
得到
然后求出最大值
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#define mem(a,b) memset(a,b,sizeof(a))
#define ll __int64
#define MAXN 1000
#define INF 0x7ffffff
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int a[1000000+10];
int sum[1000000+10];//储存每 m 个数值的和
int main()
{
int n,m,i,j,maxx,cnt;
while(scanf("%d%d",&n,&m)!=EOF)
{
mem(sum,0);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(i<=m)
sum[m]+=a[i];
else
sum[i]=sum[i-1]-a[i-m]+a[i];//以 m个单位为一组 将a[i]存入sum[i]
}
maxx=0;
cnt=m;
for(i=n;i>=n-m+1;i--)//最末尾的情况
{
maxx+=a[i]*cnt;
cnt--;
}
int s=maxx;
for(i=n-1;i>=m;i--)//从末尾往前推
{
s=s-m*a[i+1]+sum[i];
if(s>maxx)
{
maxx=s;
}
}
printf("%d
",maxx);
}
return 0;
}