Codeforces Round #877 (Div. 2) B. - Nikita and string
题目链接:http://codeforces.com/contest/877/problem/B
Nikita and string
time limit per test2 seconds
memory limit per test256 megabytes
Nikita thinks that string is beautiful if it can be cut into 3 strings (possibly empty) without changing the order of the letters, where the 1-st and the 3-rd one contain only letters “a” and the 2-nd contains only letters “b”.
Nikita wants to make the string beautiful by removing some (possibly none) of its characters, but without changing their order. What is the maximum length of the string he can get?
Input
The first line contains a non-empty string of length not greater than 5 000 containing only lowercase English letters “a” and “b”.
Output
Print a single integer — the maximum possible size of beautiful string Nikita can get.
input
abba
output
4
input
bab
output
2
Note
It the first sample the string is already beautiful.
In the second sample he needs to delete one of “b” to make it beautiful.
解题心得:
- 其实是一个很简单的dp,开始还以为是一个字符串的处理,主要是要注意下,在不能够凑成aba的情况可以空出来,当是不能再可以凑成的情况下空出。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5100;
char s[maxn];
int dp[5][maxn];
int main()
{
scanf("%s",s);
int len = strlen(s);
for(int i=0;i<len;i++)
{
dp[0][i+1] = dp[0][i] + (s[i] == 'a');
dp[1][i+1] = max(dp[1][i],dp[0][i]) + (s[i] == 'b');
dp[2][i+1] = max(dp[0][i],max(dp[1][i],dp[2][i])) + (s[i] == 'a');
}
int Max = max(dp[0][len],max(dp[1][len],dp[2][len]));
printf("%d",Max);
return 0;
}
最新文章
- Asp.Net Core--简单的授权
- PDF 补丁丁 0.4.3.1582 测试版发布:修复上一测试版的问题
- 008. asp.net mvc3.0安装文件及其安装时发生错误的解决方案
- Javascript同源策略对context.getImageData的影响
- ado.net工厂模式DbProviderFactories
- vpn连接成功后,本地无法连接外网
- 【HDOJ】1648 Keywords
- Leetcode OJ : Restore IP Addresses backtrack暴搜 C++ solution
- 第3章文件I/O总结
- Ubuntu 13.04 用Sublime Text 2 编译运行 JAVA
- Python之路Day13
- mysql5.6创建新用户并给授权指定的数据库权限
- APS期刊投稿准备: REVTex格式
- 基于angularJS搭建的管理系统
- 纯CSS箭头,气泡
- AS不能真机调试 (转)
- P4292 [WC2010]重建计划
- 阿里云提出的漏洞(Phpcms V9某处逻辑问题导致getshell漏洞解决方法)的问题
- rem &; em初探
- SpringMVC Controller 介绍及常用注解
热门文章
- Qt 2D绘图之六:图形视图框架的事件处理与传播
- Codeforces Round #396 (Div. 2) E
- Codeforces Round #397 by Kaspersky Lab and Barcelona Bootcamp (Div. 1 + Div. 2 combined) C
- vs2013缺少Mvc 怎么办?
- gem install 提示rubygems.org连接不上的问题
- MyBatis框架的XML数据访问Dao层接口的组合使用
- main函数与命令行参数
- WEB 前端菜鸟,感觉很迷茫,该怎么做?
- Java静态方法不能被覆盖
- python 相关编码[转]