[BZOJ4760][Usaco2017 Jan]Hoof, Paper, Scissors dp
2024-09-03 17:45:20
4760: [Usaco2017 Jan]Hoof, Paper, Scissors
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 136 Solved: 100
[Submit][Status][Discuss]
Description
You have probably heard of the game "Rock, Paper, Scissors". The cows like to play a similar game th
ey call "Hoof, Paper, Scissors"
你可能玩过石头剪刀布这个游戏,奶牛们也喜欢玩类似的游戏,叫做“蹄子剪刀布”
The rules of "Hoof, Paper, Scissors" are simple. Two cows play against each-other. They both count t
o three and then each simultaneously makes a gesture that represents either a hoof, a piece of paper
, or a pair of scissors. Hoof beats scissors (since a hoof can smash a pair of scissors), scissors b
eats paper (since scissors can cut paper), and paper beats hoof (since the hoof can get a papercut).
For example, if the first cow makes a "hoof" gesture and the second a "paper" gesture, then the sec
ond cow wins. Of course, it is also possible to tie, if both cows make the same gesture.
蹄子剪刀布的规则和石头剪刀布的规则是一样的,蹄子踩碎剪刀,剪刀剪布,布包蹄子
Farmer John wants to play against his prize cow, Bessie, at N games of "Hoof, Paper, Scissors" (1≤N
≤100,000). Bessie, being an expert at the game, can predict each of FJ's gestures before he makes i
t. Unfortunately, Bessie, being a cow, is also very lazy. As a result, she tends to play the same ge
sture multiple times in a row. In fact, she is only willing to switch gestures at most KK times over
the entire set of games (0≤K≤20). For example, if K=2, she might play "hoof" for the first few ga
mes, then switch to "paper" for a while, then finish the remaining games playing "hoof".
现在FJ想要和他的最机智的奶牛Bessie玩蹄子剪刀布(我也不知道FJ为什么有蹄子),一共进行了N轮(N<=1e5),B
essie,作为一个奶牛,非常的怠惰,无论她出什么,都喜欢连续的出,最多变化K次(K<=20),也就是说,对于她
所出的,记为序列f(i),记sum=有多少个i满足f(i)!=f(i-1)(i>1),而她的sum一定不会超过k
Given the sequence of gestures FJ will be playing, please determine the maximum number of games that
Bessiecan win.
现在FJ已经给出了他出的东西,你要告诉Bessie,在不确定她出的东西的情况下,她最多能赢多少次
Input
The first line of the input file contains N and K.
输入数据第一行为N,K
The remaining N lines contains FJ's gestures, each either H, P, or S
接下来N行表示FJ所出的东西,H表示hoof,P表示paper,S表示Scissors
Output
Print the maximum number of games Bessie can win, given that she can only change gestures at most KK times.
输出在变化不超过K次的前提下,最多能赢多少次
Sample Input
5 1
P
P
H
P
S
P
P
H
P
S
Sample Output
4
HINT
Source
sbdp题。
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
int n,K;
char s[];
int c[];
int f[][][];//1->0 0->2 2->1
int main() {
scanf("%d%d",&n,&K);
for(int i=;i<=n;i++) {
scanf("%s",s);
if(s[]=='H') c[i]=;
if(s[]=='P') c[i]=;
if(s[]=='S') c[i]=;
}
f[][][c[]]=;
for(int i=;i<=n;i++) {
for(int j=;j<=min(K,i);j++) {
for(int k=;k<;k++) {
if(k==c[i]) f[i][j][k]=max(f[i][j][k],f[i-][j][k]+);
else {
f[i][j][k]=f[i-][j][k];
f[i][j][c[i]]=max(f[i][j][c[i]],f[i-][j-][k]+);
}
}
}
}
int ans=;
for(int i=;i<=K;i++)
for(int j=;j<;j++) ans=max(ans,f[n][i][j]);
printf("%d",ans);
}
最新文章
- haproxy利用ACL规则封禁自定义IP地址拒绝访问
- EF CodeFirst 关系配置
- CentOS 7 搭建 LNMP
- [转]C# Winform ListView使用
- __set()与__get() 魔术方法
- CSS实现标题超出宽度省略号来表示
- IntelliJ IDEA 左侧列表设置忽略文件格式
- C++中“wchar_t* ”和“ char * ”之间的相互转换
- git命令的理解与扩展
- SpringBoot入门教程(十六)@Autowired、@Inject、@Resource
- iOS开发多线程之NSOperation
- 自制操作系统Antz(14)——实现内置编程语言(词法解析器)
- 【EF6学习笔记】(十一)实施继承
- linux 查看文件显示行号
- Android之批量加载图片OOM问题解决方案
- 关于VS中的调试信息输出
- PHP常用必备函数
- Javascript 的数据是什么数据类型?
- SQL-OVER与四种排名函数:ROW_NUMBER(),RANK(),DENSE_RANK(),NTILE()
- pc或者微信上用pdf.js在线预览pdf和word