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

FZU 2168 防守阵地 I

2024-07-16 14:10:03   224人阅读


B - 防守阵地 I
Time Limit:3000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u
Submit

Status
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

 

 

开始写blog才发现题解真的写不清楚啊= =

#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|1using 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\n",maxx);    }    return 0;}

　　


联系
我们