国产精品久久国产精麻豆99网站,久久天天躁狠狠躁夜夜躁2O2O,久久r热这里有精品视频

C++博客 :: 首頁 :: 新隨筆 :: 聯系 :: 聚合

:: 管理

posts - 100, comments - 15, trackbacks - 0

pku1159_DP

#include<iostream>
2

using namespace std;
3

#define MAX 5000
4

char str[MAX+2];
6

char re_str[MAX+2];
7

//int res[MAX+1][MAX+1]; //MLE
8

int res[2][MAX+1];
9

int n;
10

void dp()
12

{
13

int i,j;
14

for(j=0;j<=n;j++)
15

res[0][j]=j;
16

res[1][0]=1;
17

for(i=1;i<=n;i++)
18

{
19

res[i%2][0]=i;
20

for(j=1;j<=n;j++)
21

{
22

if(str[i]==re_str[j])
23

res[i%2][j]=res[(i-1)%2][j-1];
24

else{
25

res[i%2][j]=min(res[(i-1)%2][j],res[i%2][j-1])+1;
26

}
27

}
28

}
29

}
30

int main()
31

{
32

int i;
33

scanf("%d",&n);
34

for(i=1;i<=n;i++)
35

{
36

scanf(" %c",&str[i]);
37

re_str[n-i+1]=str[i];
38

}
39

dp();
40

printf("%d\n",res[n%2][n]>>1);
41

return 0;
42

}

posted on 2009-05-10 14:38 wyiu 閱讀(200) 評論(0) 編輯收藏引用所屬分類: POJ

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: poj 1061 線性同余 poj 2115 線性同余 poj 3368 rmq(st) poj 3264 RMQ poj 2352 樹狀數組 poj 1469 二分匹配 poj 2186 有向圖強連通分支 poj 2239 二分圖最大匹配 poj 3748 位運算 poj 2724 二分匹配

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

常用鏈接

留言簿(1)

隨筆分類(84)

隨筆檔案(100)

向高手學習

搜索

積分與排名

最新評論

閱讀排行榜

評論排行榜