【DP式搜索】HDU 2577——How to type

题目链接：点击打开链接

这个题比较有意思。大意是一个人要打一些字，他有两种方法，一种是Shift+字母，一种是Capslock之后打字母，这两种可以灵活应用，问打一段单词最少的按键次数。。这个题第一反应是搜索，写了个递归然后TLE。后来DISCUSS中得到了DP的思路。dp数组用二维，其中第二维表示capslock的开与关（1开0关），第一位是欲打的第i个字母，不断比较按capslock的方式和按shift的方式，(别忘了每一步都要得出结果，中间状态也要存储起来）最后得出哪个最短，还有线段树/树状数组方法，感觉过于繁琐了。

千万别忘了最后还得使capslock保持熄灭状态！

#include <iostream>#include <string>#include <cstring>#include <ctype.h>using namespace std;int min(int a,int b){return a<b?a:b;}int dp[105][2];int main(){int testcase;cin>>testcase;while(testcase--){memset(dp,0,sizeof(0));dp[0][1]=1;//不要忘了设定初始值 string tar;cin>>tar;int strlength=tar.size();for(int i=0;i<strlength;i++){if(islower(tar[i])){dp[i+1][0]=min(dp[i][0]+1,dp[i][1]+2);  //例：第一个是指在capslock关闭的情况下输入小写字母，只需按一下，+1//例：第二个是指在capslock打开的情况下输入小写字母，capslock->字母，+2 dp[i+1][1]=min(dp[i][0]+2,dp[i][1]+2);//这里第一个是capslock->字母,第二个是shift+字母,终态永远是左边，故+2 }else{dp[i+1][0]=min(dp[i][0]+2,dp[i][1]+2);dp[i+1][1]=min(dp[i][0]+2,dp[i][1]+1);}}if(dp[strlength][0]<(dp[strlength][1]+1)){cout<<dp[strlength][0]<<endl;}else{cout<<dp[strlength][1]+1<<endl;}}}