【动态规划】Überwatch
2024-10-06 08:52:44
Überwatch
题目描述
The lectures are over, the assignments complete and even those pesky teaching assistants have nothing left to criticize about your coding project. Time to play some video games! As always, your procrastinating self has perfect timing: Cold Weather Entertainment just released Überwatch, a competitive first person video game!
Sadly, you aren’t very good at these kind of games. However, Überwatch offers more than just skill based gameplay. In Überwatch you can defeat all opponents in view with a single button press using your ultimate attack. The drawback of this attack is that it has to charge over time before it is ready to use. When it is fully charged you can use it at any time of your choosing.
After its use it immediately begins to charge again.
With this knowledge you quickly decide on a strategy:
• Hide from your opponents and wait for your ultimate attack to charge.
• Wait for the right moment.
• Defeat all opponents in view with your ultimate attack.
• Repeat.
After the game your teammates congratulate you on your substantial contribution. But you wonder: How many opponents could you have defeated with optimal timing?
The game is observed over n time slices. The ultimate attack is initially not charged and requires m time slices to charge. This first possible use of the ultimate attack is therefore in the (m+1)-th time slice. If the ultimate attack is used in the i-th time slice, it immediately begins charging again and is ready to be fired in the (i + m)-th time slice.
Sadly, you aren’t very good at these kind of games. However, Überwatch offers more than just skill based gameplay. In Überwatch you can defeat all opponents in view with a single button press using your ultimate attack. The drawback of this attack is that it has to charge over time before it is ready to use. When it is fully charged you can use it at any time of your choosing.
After its use it immediately begins to charge again.
With this knowledge you quickly decide on a strategy:
• Hide from your opponents and wait for your ultimate attack to charge.
• Wait for the right moment.
• Defeat all opponents in view with your ultimate attack.
• Repeat.
After the game your teammates congratulate you on your substantial contribution. But you wonder: How many opponents could you have defeated with optimal timing?
The game is observed over n time slices. The ultimate attack is initially not charged and requires m time slices to charge. This first possible use of the ultimate attack is therefore in the (m+1)-th time slice. If the ultimate attack is used in the i-th time slice, it immediately begins charging again and is ready to be fired in the (i + m)-th time slice.
输入
The input consists of:
• one line with two integers n and m, where
– n (1 ≤ n ≤ 300 000) is the game duration;
– m (1 ≤ m ≤ 10) is the time needed to charge the ultimate attack in time slices.
• one line with n integers xi (0 ≤ xi ≤ 32) describing the number of opponents in view during a time slice in order.
• one line with two integers n and m, where
– n (1 ≤ n ≤ 300 000) is the game duration;
– m (1 ≤ m ≤ 10) is the time needed to charge the ultimate attack in time slices.
• one line with n integers xi (0 ≤ xi ≤ 32) describing the number of opponents in view during a time slice in order.
输出
Output the maximum number of opponents you can defeat.
样例输入
4 2
1 1 1 1
样例输出
1
【题解】
题意说,有一个大招每次放完还需要等待m次,直接考虑dp[i],从开始到i这个时间内获取的最大值。
注意:第一个位置的时候为0,然后如果放完大招后下一次充能从1开始。【题目说得很清楚】
This first possible use of the ultimate attack is therefore in the (m+1)-th time slice.
If the ultimate attack is used in the i-th time slice, it immediately begins charging again and is ready to be fired in the (i + m)-th time slice.
然后直接转移即可。
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+;
int dp[N],a[N],n,m;
int main()
{
scanf("%d%d",&n,&m);
//m++;
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
int res = ;
for(int i=;i<=n;i++){
dp[i] = dp[i-] ;
if( i>=(m+) ){
dp[i] = max( dp[i-m] + a[i] , dp[i] );
res = max( res , dp[i]) ;
}
}
printf("%d\n",res );
return ;
}
最新文章
- maven和svn区别
- Linux第03天
- codeforces 83 D. Numbers
- redis存在大量脏页问题的追查记录
- Xcode 移除(卸载)插件
- NDK(5) Android JNI官方综合教程[JavaVM and JNIEnv,Threads ,jclass, jmethodID, and jfieldID,UTF-8 and UTF-16 Strings,Exceptions,Native Libraries等等]
- linux grep和正则表达式
- 使用java注解的例子有没有
- Fastreport怎么样在同一页上下部分打印相同内容
- 洛谷-三连击(升级版)-BOSS战-入门综合练习1
- Android编程中的实用快捷键
- css代码初始化
- 2018年最值得关注的30个Vue开源项目
- 遍历List过程中删除操作报java.util.ConcurrentModificationException错误
- MyBatis:一对多关联查询
- webstorm 智能提示忽略大小写
- PHP函数可变参数
- 利用matlab求图像均值和方差的几种方法
- ASP.NET Identity系列02,在ASP.NET MVC中增删改查用户
- Android Studio 出现 Gradle&#39;s dependency cache may be corrupt 错误分析