FZU2168——防守阵地 I——————【找规律或前缀和】

防守阵地 I

Time Limit:3000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Submit Status Practice FZU 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

解题思路：方法1>通过求解两次前缀和，然后遍历求出最大值

　　　

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 using namespace std;

 const int maxn=;

 #define  ll long long

 ll x[maxn];

 ll a[maxn];

 ll sum[maxn];

 int main(){

     int n,m;

     while(scanf("%d%d",&n,&m)!=EOF){

         for(int i=;i<=n;i++){

             scanf("%d",&x[i]);

         }

         for(int i=n;i>=;i--){

             a[n-i+]=x[i]+a[n-i];

         }

         for(int i=;i<=n;i++){

             sum[i]=a[i]+sum[i-];

         }

         ll ans=;

         for(int i=m;i<=n;i++){

             ans=max(sum[i]-sum[i-m]-m*a[i-m],ans);

         }

         printf("%lld\n",ans);

     }

 }

方法2>求一次前缀和，然后求出m个元素的和，找规律发现，a+2b+3c..mx-(a+b+c...+x)+my=b+2c+3d...my。

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

const int maxn=1000100;

int a[maxn],sum[maxn],sam[maxn];

int main(){

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF){

        for(int i=1;i<=n;i++){

            scanf("%d",&a[i]);

        }

        for(int i=1;i<=n;i++)

            sam[i]=sam[i-1]+a[i];

        for(int i=1;i<=n-m+1;i++){

            sum[i]=sam[i+m-1]-sam[i-1];

        }

        int ans=0,tmp=0;

        for(int i=1;i<=m;i++)

            tmp+=a[i]*i;

        for(int i=2;i<=n-m+1;i++){

            ans=max(ans,tmp-sum[i-1]+m*a[i+m-1]);

            tmp=tmp-sum[i-1]+m*a[i+m-1];

        }

       printf("%d\n",ans);

    }

    return 0;

}