FZU 2168 防守阵地I (模拟 简单规律)

部队中共有N个士兵，每个士兵有各自的能力指数Xi，在一次演练中，指挥部确定了M个需要防守的地点，按重要程度从低到高排序，依次以数字1到M标注每个地点的重要程度，指挥部将选择M个士兵依次进入指定地点进行防守任务，能力指数为X的士兵防守重要程度为Y的地点将得到X*Y的参考指数。现在士兵们排成一排，请你选择出连续的M个士兵依次参加防守,使得总的参考指数值最大。

输入包含多组数据。

输入第一行有两个整数N,M(1<=N<=1000000，1<=M<=1000),第二行N个整数表示每个士兵对应的能力指数Xi（1<=Xi<=1000）。

对于30%的数据1<=M<=N<=1000。

输出一个整数，为最大的参考指数总和。

5 32 1 3 1 4Sample Output
17注意读题，是连续的士兵。找到规律，模拟士兵的选取过程，遍历所有士兵，过程维护中最大值，时间复杂度为o（n）。规律：以样例数据为例，第一组数据，2*1+1*2+3*3，第二组数据，1*1+3*2+1*3。可以看出第二组就是第一组减去，2 1 3三个数的和再加上第四个数乘以m。比较抽象，建议手动模拟几组数据，这样比较容易理解。模拟就是按照规律模拟的。详细见代码。AC代码：
#include <iostream>#include <math.h>#include <algorithm>#include <string.h>#include <stdio.h>using namespace std;long long n,m,hum[1000005],sum,peo,i,tmax;int main(){    while(~scanf("%lld%lld",&n,&m))    {        for(i=1; i<=n; i++)        {            scanf("%lld",&hum[i]);        }        sum=0;peo=0;        for(i=1;i<=m;i++)        {            sum+=hum[i]*i;            peo+=hum[i];每次减去的m个人的能力指数的和        }        tmax=sum;        for(i=m+1;i<=n;i++)        {            sum=sum-peo+hum[i]*m;模拟的过程            peo=peo-hum[i-m]+hum[i];维护m个人的能力指数的和            tmax=max(sum,tmax);        }        PRintf("%lld/n",tmax);    }    return 0;}