首页 > 代码库 > FZU 2168 防守阵地 I
FZU 2168 防守阵地 I
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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。