输入状态HDU 2577 动态规划(DP) How to Type

上班之余抽点时间出来写写博文，希望对新接触的朋友有帮助。今天在这里和大家一起学习一下输入状态

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2577

分析：

１．要想晓得输入n个字母时最小的按键数，必须先求输入n-1个字母时的最小按键数．所以，要从前今后把每输入一个字母的最小按键数都算出来．

２. 每次输入时都只有两种状态(CapsLock on与off, Shift另外考虑)，所以只要求出每次输入时候别在这两种状态下的最小值，便可求出输入下一个的最小值．

３. 初始时，i=0，状态为off，所以on[0]=1 (要变为on状态必须按下CapsLock) off[0]=0；

４. 当第i个要输入的是大写字母：

a．如果输入前的状态为on时，若要使得输入后坚持on状态，只按一下即可，若要使得输入后坚持off状态，则要按两下．

b．如果输入前的状态为off时，若要使得输入后坚持on状态，最少要按两下，若要使得输入后坚持off状态，也最小要按两下(加Shift)．

５. 当第i个要输入的是小写字母时，与4相似．

每日一道理
生活的无奈，有时并不源于自我，别人无心的筑就，那是一种阴差阳错。生活本就是矛盾的，白天与黑夜间的距离，春夏秋冬之间的轮回，于是有了挑剔的喜爱，让无奈加上了喜悦的等待。

#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<iomanip>

using namespace std;
const int maxn=100000;

int on[105]={1};
int off[105]={0};

int main() {
    int T; cin>>T;
    while(T--) {
        string s; cin>>s;
        int len=s.size();
        for(int i=0,q=0; i<len; ++i) {
            if(s[i]>='A'&&s[i]<='Z'){
                on[i+1]=min( on[i]+1, off[i]+2 );
                off[i+1]=min( on[i]+2, off[i]+2 );
            }
            else {
                on[i+1]=min( on[i]+2, off[i]+2 );
                off[i+1]=min( on[i]+2, off[i]+1 );
            }
        }
        on[len]++;///最后要坚持关灯状态
        cout<<min(on[len],off[len])<<endl;
    }
    return 0;
}

文章结束给大家分享下程序员的一些笑话语录：雅虎最擅长的不是开通新业务，是关闭旧业务。