HDU2577 How to Type【DP】
2024-08-30 20:41:47
题目链接:
题目大意:
给你一个仅仅包括大写和小写字母的字符串,如今Pirates要从键盘上输出它。按CapsLk可开
启关闭大写和小写指示灯。
按Shift可转换将输入字母的大写和小写而不改变CapsLk的开关状态。Pirates有
一个坏习惯,假设输入的时候CapsLk是开着的,那么输入结束后必须把它关闭。
问,输入一个字符
串,最小的按键数目是多少
思路:
用两个数组dpa和dpb分别来表示CapsLk关闭状态和开启状态的最小操作数。
假设将要输入的字母是小写字母:
dpa[i+1] = min(dpa[i]+1,dpb[i]+2); 不开灯的情况下直接按字母,开灯情况则先关灯再按字母
dpb[i+1] = min(dpa[i]+2,dpb[i]+2); 不开灯的情况下按字母再开灯。开灯情况下Shift+按字母,
最后保持开灯状态
假设将要输入的字母是大写字母:
dpa[i+1] = min(dpa[i]+2,dpb[i]+2); 不开灯的情况下按Shift+字母,开灯情况下则按字母再关灯
dpb[i+1] = min(dpa[i]+2,dpb[i]+1); 不开灯的情况下开灯按字母。开灯情况下直接按字母
最后dpb[len]++,要把灯关掉。
初始化为dpa[0] = 0。dpb[0] = 1,由于dpb状态刚開始要开灯。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; int dpa[110],dpb[110];
char a[110]; int main()
{
int T;
scanf("%d",&T);
while(T--)
{
getchar();
scanf("%s",a);
memset(dpa,0,sizeof(dpa));
memset(dpb,0,sizeof(dpb));
dpa[0] = 0;//dpa为关灯状态最小操作数
dpb[0] = 1;//dpb为开灯状态最小操作数
int len = strlen(a);
for(int i = 0; i < len; i++)
{
if(a[i]>='a' && a[i]<='z')
{
dpa[i+1] = min(dpa[i]+1,dpb[i]+2);
dpb[i+1] = min(dpa[i]+2,dpb[i]+2);
}
else
{
dpa[i+1] = min(dpa[i]+2,dpb[i]+2);
dpb[i+1] = min(dpa[i]+2,dpb[i]+1);
}
}
dpb[len]++;
int ans = min(dpa[len],dpb[len]);
printf("%d\n",ans);
}
return 0;
}
最新文章
- Qt5+VS2012编程
- HDU1002 -A + B Problem II(大数a+b)
- jquery学习以及下载链接
- NPOI 生成 excel基本设置
- [转载]常见slave 延迟原因以及解决方法
- Tomcat配置SSL后使用HTTP后跳转到HTTPS
- VS编写一个项目的路径规划
- TJOI2011书架(dp)
- centos7系统排错
- js方法参数中含有单引号双引号的处理
- Confluence 6 自定义 Decorator 模板的宏和针对高级用户
- 以太坊钱包开发系列2 - 账号Keystore文件导入导出
- 完整安装always on 集群
- 在Java Web程序中使用监听器可以通过以下两种方法
- redmine和jenkins的ldap登录设置
- 【第六课】Nginx常用配置下详解
- 每位架构师都应该熟知的 10 个 SOA 设计模式
- 我对NHibernate的感受(3):有些尴尬的集合支持
- mysql.sock文件丢失被删除解决方法
- log4php使用及配置
热门文章
- libevent学习之网络通信
- bat2exe 就是这么简单 白研究半天VC++了
- windows环境开启PHP fileinfo扩展
- TCP/IP 协议分层
- Uncaught TypeError: Cannot assign to read only property &#39;exports&#39; of object &#39;#<;Object>;&#39;
- gifsicle for linux ----------gif 图像处理
- 安装Yellowfin报错——No such file or directory: &#39;/tmp/pip-build-jykvuD/YellowFin/README.md&#39;
- Python的前世今生
- hdfs深入:02、今日课程内容大纲以及hdfs的基本实现
- Git中文书籍