HDU 2577 How to Type(dp)

HDU 2577 How to Type(dp)"/>

HDU 2577 How to Type(dp)

题目链接：HDU 2577 How to Type

dp。

notlock[i]表示type第i个字母后大写锁定键为关闭状态的最少type次数，lock[i]表示type第i个字母后大写锁定键为开启状态的最少type次数。

状态转移方程：

s[i]为大写字母：

lock[i] = min(lock[i - 1] + 1,notlock[i - 1] + 2);
notlock[i] = min(notlock[i - 1] + 2,lock[i - 1] + 2);

s[i]为小写字母：

lock[i] = min(lock[i - 1] + 2,notlock[i - 1] + 2);
notlock[i] = min(lock[i - 1] + 2,notlock[i - 1] + 1);

最后输出时候需要判断一下notlock[len - 1] 和 lock[len - 1] + 1的大小。

#include <iostream>
#include <cstring>using namespace std;
const int MAX_N = 100 + 10;
int notlock[MAX_N],lock[MAX_N];
int t;
char s[MAX_N];int main()
{cin >> t;while(t--){memset(notlock,0,sizeof(notlock));memset(lock,0,sizeof(lock));cin >> s;int len = strlen(s);if(s[0] >= 'A' && s[0] <= 'Z')lock[0] = notlock[0] = 2;else{lock[0] = 2;notlock[0] = 1;}for(int i = 1;i < len;i++){if(s[i] >= 'A' && s[i] <= 'Z'){lock[i] = min(lock[i - 1] + 1,notlock[i - 1] + 2);notlock[i] = min(notlock[i - 1] + 2,lock[i - 1] + 2);}else{lock[i] = min(lock[i - 1] + 2,notlock[i - 1] + 2);notlock[i] = min(lock[i - 1] + 2,notlock[i - 1] + 1);}}cout << (notlock[len - 1] < lock[len - 1] + 1 ? notlock[len - 1] : lock[len - 1] + 1) << endl;}return 0;
}