按键

Description

在计算机键盘上输出一串字符需要一定的按键数目。假定初始为小写字母状态，结束之后也必须回到小写字母状态。例如，在输入字符串“Pirates”时，需要先按下Shift+P,再依次按下i,r,a,t,e,s，一共需要按8次键；而在输入字符串“PKUACM”时，最少也需要8次，即先按Caps Lock键，再按下p,k,u,a,c,m，最后再按一次Caps Lock键。下面输出若干个字符串，求它们的最少按键次数。

Input

第一行为正整数p(≤100)，表示测试数据组数。接下来p行，每行一个不长度不超过100的字符串。

Output

对于每组数据，输出一个正整数表示最少按键次数。

Sample Input

2 Pirates PKUACM

Sample Output

8 8

题解

水题，区间DP。 f[i][j][k]为从i到j开始结束状态为k的最少按键次数。 k=0...3 ，0代表开始小写结束小写，1代表开始小写结束大写，以此类推。 转移就是一般区间DP的转移。

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N = 100 + 10; int a[N], f[N][N][4]; int p, n; void init(){ char s[N]; scanf("%s", s + 1); n = strlen(s + 1); memset(f, 0x3f, sizeof(f)); for(int i = 1; i <= n; i++) if(s[i] >= 'a' && s[i] <= 'z') a[i] = 0, f[i][i][0] = 1, f[i][i][1] = f[i][i][2] = f[i][i][3] = 2; else a[i] = 1, f[i][i][0] = f[i][i][1] = f[i][i][2] = 2, f[i][i][3] = 1; } void work(){ scanf("%d", &p); while(p--){ init(); for(int l = 1; l <= n; l++){ for(int i = 1; i + l <= n; i++){ int j = i + l; for(int k = i; k + 1 <= j; k++){ f[i][j][0] = min(f[i][k][0] + f[k+1][j][0], f[i][k][1] + f[k+1][j][2]); f[i][j][1] = min(f[i][k][0] + f[k+1][j][1], f[i][k][1] + f[k+1][j][3]); f[i][j][2] = min(f[i][k][2] + f[k+1][j][0], f[i][k][3] + f[k+1][j][2]); f[i][j][3] = min(f[i][k][2] + f[k+1][j][1], f[i][k][3] + f[k+1][j][3]); } } } printf("%d\n", f[1][n][0]); } } int main(){ freopen("key.in", "r", stdin); freopen("key.out", "w", stdout); work(); return 0; }

ps. 想麻烦了，还有 O(N) 的解法。 设f[i][[k]为从1到i末状态为k的所需要的按键数，k为0代表小写状态，k为1代表大写状态。 那么s[i]如果为小写，那么f[i][0]可以从f[i-1][0]+1或f[i-1][1]+2转移得到，f[i][1]可以从f[i-1][0]+2或f[i-1][1]+2转移得到。 s[i]如果为大写同理转移。