http://acm.hdu.edu.cn/showproblem.php?pid=2577
#include<iostream> using namespace std; #define N 101 int main(void) { char ch[N]; int dp_close[N],dp_open[N]; int t; scanf("%d",&t); while(t--) { scanf("%s",ch); int len=strlen(ch)-1; dp_open[0]=2; if(ch[0]>='a'&&ch[0]<='z') dp_close[0]=1; else dp_close[0]=2; for(int i=1;i<=len;i++) { if(ch[i]>='a'&&ch[i]<='z') { dp_open[i]=min(dp_open[i-1]+2,dp_close[i-1]+2); dp_close[i]=min(dp_close[i-1]+1,dp_open[i-1]+2); } else { dp_open[i]=min(dp_open[i-1]+1,dp_close[i-1]+2); dp_close[i]=min(dp_close[i-1]+2,dp_open[i-1]+2); } } printf("%d/n",min(dp_close[len],dp_open[len]+1)); } }
简单的DP，dp_close[]代表大写锁定关，dp_open[]代表大写锁定开。
若当前字母为大写，DP方程为： dp_open[i]=min(dp_open[i-1]+1,dp_close[i-1]+2);
dp_close[i]=min(dp_close[i-1]+2,dp_open[i-1]+2);
若当前字母为小写，Dp方程为： dp_open[i]=min(dp_open[i-1]+2,dp_close[i-1]+2);
dp_close[i]=min(dp_close[i-1]+1,dp_open[i-1]+2);
