FZU_Problem 2168 防守阵地 I
2024-08-31 13:02:04
Problem 2168 防守阵地 I
Accept: 128 Submit: 392
Time Limit: 3000 mSec Memory Limit : 32768 KB
Problem 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-m个士兵当前能力指数x为1*a[1]+2*a[2]+3*a[3]+.....+m*a[m]。那么easy得出前2-m+1个士兵的能力指数y为:x+a[m+1]*m-(a[1]+a[2]+.....a[m]);
后面这个仅仅要输入时预处理一下即可,这样就枚举出连续m个士兵的全部情况。然后取最大值。
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 1000010
int a[maxn],b[maxn];
int main()
{
int n,m,i;
__int64 ans,x,temp;
while(scanf("%d%d",&n,&m)!=EOF)
{
ans=0;
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
b[i]=b[i-1]+a[i]; //保存前i个数的和
if(i<=m) ans+=a[i]*i; //1-m个士兵的能力指数
}
x=ans;
for(i=m+1;i<=n;i++)
{
temp=x+(m+1)*a[i]; //多加一次a[i]
temp-=b[i]-b[i-m-1]; //由于b[i]包括了a[i],等于这多减了一次,所以上面多加一次
x=temp; //传递到下一阶段
ans=max(temp,ans); //不断更新取最大值
}
printf("%I64d\n",ans);
}
return 0;
}
最新文章
- easyui表格的增删改查
- 【Unity3D】利用Shader以及更改Mesh实现2D游戏的动态阴影效果
- 20145320 《Java程序设计》第2周学习总结
- 【leetcode❤python】242. Valid Anagram
- SASS学习笔记1 —— 安装、编译和调试
- Android studio中Rendering Problems不能可视化操作的解决办法
- onclick用法 超链接简单弹出窗口实例
- c语言中gets ,getschar 和fgets 的用法及三者之间的差别
- Flex Cairngrom框架浅浅印象
- H5学习的第三周
- 创建一个dynamics 365 CRM online plugin (十) - Isolation mode or trust mode
- C# 动态输出Dos命令执行结果
- 全方位理解Android权限之底层实现概览
- gym 101873
- C#USB设备枚举Kernel32的PInvoke
- bzoj 2440 完全平方数 【莫比乌斯函数】
- 通过命令更新git for windows
- reload基础
- java导出word文件
- [转载]java调用本地dos命令
热门文章
- 在Eclipse中创建Maven多模块项目
- PPAPI插件与浏览器的通信
- C++数值类型极限值的获取
- Mac OSX Yosemite 10.10 brew 错误:mktemp: mkdtemp failed on /tmp/git-LIPo: No such file or directory
- JavaScript的闭包理解
- SpringMVC-Interceptor拦截Session登录
- 请求测试——Fiddler2工具(可以测试POST和Get)
- .NET中的异步操作及线程同步
- GradientDrawable类的利用动态设置样式中的颜色
- Java 自带MD5 校验文件