hdu2577 How to Type ——DP入门题

May 10, 2013
Hdu DP

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2577 题目大意：　　一个人打字，有小写字母，有大写字母，并且要求打完字以后要把CapsLock键关掉。求最少的按键次数。题目思路：　　dp[i][0]表示打到第 i 个字母的时候，CapsLock键是关着的；　　dp[i][1]表示打到第 i 个字母的时候，CapsLock键是开着的；　　然后就是判断下一个字母是大写字母还是小写字母，如果是小写字母，dp[i+1][0] = min(dp[i][0] + 1, dp[i][1] + 2); 表示，要求下一个状态CapsLock关着，那么前一个状态如果是关着的，直接打字母就可以了，所以只需要加1，如果是开着的，就要先把CapsLock关掉，然后再打字母，所以需要加2. 其他的情况类似。参考的是这个人的代码：http://www.cnblogs.com/mengxm-lincf/archive/2011/06/07/2074489.html


#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <algorithm>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long int LL;
const int MAXN =  0x7fffffff;
const int  MINN =  -0x7fffffff;
const double eps = 1e-9;
const int dir[8][2] = {{0,1},{1,0},{0,-1},{-1,0},{-1,1},
  {1,1},{1,-1},{-1,-1}};

int dp[110][2]; char ch[110];
int main(void){
#ifndef ONLINE_JUDGE
  freopen("hdu2577.in", "r", stdin);
#endif
  int t; scanf("%d", &t);
  while (t--) {
    scanf("%s", ch); int len = strlen(ch), i;
    memset(dp, 0, sizeof(dp)); dp[0][1] = 1;
    for (i = 0; i < len; ++i) {
      if (islower(ch[i])) {
        dp[i+1][0] = min(dp[i][0] + 1, dp[i][1] + 2);
        dp[i+1][1] = min(dp[i][0] + 2, dp[i][1] + 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);
      }
    }
    printf("%d\n", min(dp[len][0], dp[len][1] + 1));
  }

  return 0;
}

　　这道DP感觉挺有意思~

Read more