首页 > 代码库 > 防守阵地 I

防守阵地 I

2024-08-09 18:47:14   220人阅读

                                                      防守阵地 I

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 32 1 3 1 4

Sample Output

17
  思路：
         a+2b+3c+4d+5e
可以写成 a+b+c+d+e    sum[5]
           b+c+d+e    sun[5]-sum[1]
             c+d+e    sum[5]-sum[2]
               d+e    sum[5]-sum[3]
                 e    sum[5]-sum[4]
        sum[n] 代表前n项和，s[n]代表前n个sum和
  所以 ： 
         a+2b+3c+4d+5e=5*sum[5]-(sum[1]+sum[2]+sum[3]+sum[4])
                      =5*sum[5]-(s[2]-s[1]+s[3]-s[2]+s[4]-s[3])
                      =5*sum[5]-s[4]
所以可以推导出：ans=m*sum[i-1]-(s[i-1]-s[i-1-m]) 

#include<stdio.h>
#include<string.h>
int sum[1000005],s[1000005];
int main()
{
  int n,m,i,x,max;
  while(scanf("%d%d",&n,&m)!=EOF)
  {
      max=0;
     memset(sum,0,sizeof(sum));
     memset(s,0,sizeof(s));
     sum[0]=s[0]=0;
     for(i=1;i<=n;i++)
      {
      scanf("%d",&x);
      sum[i]=sum[i-1]+x;
      s[i]=s[i-1]+sum[i]; 
      }            
      
       if(n<m) {printf("%d\n",s[n]);continue;}
       for(i=m;i<=n;i++)
       {
         int ans=m*sum[i]-s[i-1]+s[i-m-1];
         if(ans>max) max=ans;                 
       }          
       printf("%d\n",max);
  }
return 0;
}


防守阵地 I


联系
我们