首页 > 代码库 > HDU2577dp基础

HDU2577dp基础

最近广州很热啊,住在楼顶7楼的我真心热,听闻不超过八层不建电梯,所以我们就悲剧了,每天都爬七楼,不过早已习惯了,但是一身汗有木有!

今天早上做的还是dp,题目的意思就是输出一串含大小写字符串,最小键入次数,平时我只用caps来切换大小写简直无法直视这题目……

后来shift切换大小写这点让我小小郁闷

代码注释打得很清晰,话说我比赛时候都会打注释的……因为怕乱。上课了!

/***********************************************************
	> OS     : Linux 3.2.0-60-generic #91-Ubuntu
	> Author : yaolong
	> Mail   : dengyaolong@yeah.net 
	> Time   : 2014年05月27日 星期二 07:09:19
 **********************************************************/
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
int a[105],b[105];//a为关灯,b为开灯
int main(){
   // freopen("in.txt","r",stdin);
    string str;
    int T;
    cin>>T ;   
    while(T--){
            
        cin>>str;
        int len=str.length();
        memset(a,0,sizeof(a));
        memset(b,0,sizeof(b));
        if(str[0]<'a'){//大写
            a[0]=2;//保持小写,就直接shift
            b[0]=2;//caps+直接输入
        }else{//小写
            a[0]=1;//保持小写,直接输入
            b[0]=2;//先输入,再 caps


        }
        for(int i=1;i<len;i++){
            if(str[i]<'a'){//大写
                a[i]=min(a[i-1]+2,b[i-1]+2);//如果是关了又保持关的,当然是按shift,即+2,开了的直接打,打完关灯
                b[i]=min(a[i-1]+2,b[i-1]+1);//关了的开了打
            }else{//小写
                a[i]=min(a[i-1]+1,b[i-1]+2);//没开直接打;开了按 cap再输入
                b[i]=min(a[i-1]+2,b[i-1]+2);//没开按输入后再cap,开了的,直接shift.
            }
        }
        cout<<min(a[len-1],b[len-1]+1)<<endl;
    }
    return 0;
}