纠结啊，几天找不到个可做的题，前几天刷了几个水题，第300个也是水题，终于300了，加油！
写的太搓了。。。写的很暴力，不过数据量小，水过吧。。
1 #include2 #include 3 #include 4 #define N 100000000 5 int main() 6 { 7 char p[300]; 8 int dp[300],sum[300]; 9 int i,j,len,t,min;10 scanf("%d%*c",&t);11 while(t--)12 {13 memset(sum,0,sizeof(sum));14 memset(dp,0,sizeof(dp));15 scanf("%s",p);16 len = strlen(p);17 if(p[0] <= 'Z'&&p[0] >= 'A')18 sum[0] = 1;19 for(i = 1; i <= len-1; i ++)20 {21 if(p[i] <= 'Z'&&p[i] >= 'A')22 sum[i] = sum[i-1] + 1;23 else24 sum[i] = sum[i-1];25 }26 for(i = 0; i <= len-1; i ++)27 {28 min = N;29 for(j = 0; j <= i; j ++)30 {31 if(j == 0)32 {33 if(min > sum[i]+2+2*(i-sum[i]+1))34 min = sum[i]+2+2*(i-sum[i]+1);35 if(min > 2*sum[i]+i-sum[i]+1)36 min = 2*sum[i]+i-sum[i]+1;37 }38 else39 {40 if(min > dp[j-1] + (sum[i]-sum[j-1])+2+2*(i-j+1-sum[i]+sum[j-1]))41 min = dp[j-1] + (sum[i]-sum[j-1])+2+2*(i-j+1-sum[i]+sum[j-1]);42 if(min > dp[j-1] + (sum[i]-sum[j-1])*2 + i-j+1-sum[i]+sum[j-1])43 min = dp[j-1] + (sum[i]-sum[j-1])*2 + i-j+1-sum[i]+sum[j-1];44 }45 }46 dp[i] = min;47 }48 printf("%d\n",dp[len-1]);49 }50 return 0;51 }