http://acm.hdu.edu.cn/showproblem.php?pid=2577

此題為本人第一次自主分析動(dòng)態(tài)規(guī)劃。

對(duì)于每個(gè)字母之前的字母有兩種狀態(tài) 1.tab開(kāi)啟 2.tab沒(méi)有開(kāi)啟，有數(shù)組分別記錄兩種狀態(tài)下的最短時(shí)間，接下來(lái)狀態(tài)轉(zhuǎn)移方程：

0代表沒(méi)開(kāi)，1代表開(kāi)了，對(duì)當(dāng)前字母分類(lèi)

小寫(xiě)字母：??????????????? timer[i+1][0]=min(timer[i][0]+1,timer[i][1]+2);
??????????????????????????? ? timer[i+1][1]=min(timer[i][0]+2,timer[i][1]+2);

大寫(xiě)字母：??????????????? timer[i+1][0]=min(timer[i][0]+2,timer[i][1]+2);
????????????????????????????? timer[i+1][1]=min(timer[i][0]+2,timer[i][1]+1);

1 #include<stdio.h>
2 #include<string.h>
3 char str[110];
4 int timer[120][2];
5 #define min(a,b) (a)<(b)?(a):(b)
6 int main()
7 {
8 int num;
9 scanf("%d\n",&num);
10 while(num--)
11 {
12 gets(str);
13 int len=strlen(str);
14 memset(timer,0,sizeof(timer));
15 timer[0][1]=1;
16 for(int i=0;i<len;i++)
17 {
18 if(str[i]>='a'&&str[i]<='z')
19 {
20 timer[i+1][0]=min(timer[i][0]+1,timer[i][1]+2);
21 timer[i+1][1]=min(timer[i][0]+2,timer[i][1]+2);
22 }
23 else
24 {
25 timer[i+1][0]=min(timer[i][0]+2,timer[i][1]+2);
26 timer[i+1][1]=min(timer[i][0]+2,timer[i][1]+1);
27 }
28 }
29 printf("%d\n",min(timer[len][0],timer[len][1]+1)); //此處在tab開(kāi)啟狀態(tài)時(shí)加1表示最后結(jié)尾要關(guān)閉tab鍵
30 }
31 return 0;
32 }

轉(zhuǎn)載于:https://www.cnblogs.com/mengxm-lincf/archive/2011/06/07/2074489.html

總結(jié)

以上是生活随笔為你收集整理的HDU2577的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。