欧美成人免费全部,国产婷婷色一区二区三区在线 ,欧美国产日本高清在线

[動態規劃]pku1141

int f[i][j]表示第i個字符到第j個字符需要添加的最少括號數。string ans[i][j] 表示第i個字符到第j個字符按照最優方案添加括號后的串。狀態轉移：1.f[i][j]由f[i + 1][j - 1]轉移來（通過兩端添括號() / [] ）。2.f[i][j]由f[i][k] + f[k + 1][j]轉移來（通過串合并）。答案是ans[0][len - 1]。

/*************************************************************************

Author: WHU_GCC

Created Time: 2007-8-27 9:54:57

File Name: pku1141.cpp

Description:

************************************************************************/

#include <iostream>

using namespace std;

#define out(x) (cout << #x << ": " << x << endl)

const int maxint = 0x7FFFFFFF;

typedef long long int64;

const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;

template <class T> void show(T a, int n) {for (int i = 0; i < n; ++i) cout << a[i] << ' '; cout << endl; }

template <class T> void show(T a, int r, int l) {for (int i = 0; i < r; ++i) show(a[i], l); cout << endl; }

const int maxn = 110;

char s[maxn];

int len;

int f[maxn][maxn];

string ans[maxn][maxn];

void dp()

{

memset(f, 0, sizeof(f));

for (int i = 0; i < len; i++)

for (int j = i; j < len; j++)

{

f[i][j] = maxint;

ans[i][j] = "";

}

for (int i = len - 1; i >= 0; i--)

for (int j = i; j < len; j++)

if (i == j)

{

f[i][j] = 1;

if (s[i] == '(') ans[i][j] = "()";

if (s[i] == ')') ans[i][j] = "()";

if (s[i] == '[') ans[i][j] = "[]";

if (s[i] == ']') ans[i][j] = "[]";

}

else

{

if (j > i)

{

if (s[i] == '(' && s[j] == ')')

{

if (f[i + 1][j - 1] < f[i][j])

{

f[i][j] = f[i + 1][j - 1];

ans[i][j] = "(" + ans[i + 1][j - 1] + ")";

}

else if (s[i] == '[' && s[j] == ']')

{

if (f[i + 1][j - 1] < f[i][j])

{

f[i][j] = f[i + 1][j - 1];

ans[i][j] = "[" + ans[i + 1][j - 1] + "]";

}

for (int k = i; k < j; k++)

{

if (f[i][k] + f[k + 1][j] < f[i][j])

{

f[i][j] = f[i][k] + f[k + 1][j];

ans[i][j] = ans[i][k] + ans[k + 1][j];

}

int main()

{

while (scanf("%s", s) != EOF)

{

len = strlen(s);

dp();

cout << ans[0][len - 1] << endl;

}

return 0;

}

posted on 2007-08-27 15:55 Felicia 閱讀(1261) 評論(3) 編輯收藏引用所屬分類: 動態規劃

Comments

# re: [動態規劃]pku1141
l-y-p
Posted @ 2008-03-03 11:36
你的這個代碼提交也WA，不知是怎么回事，自己也寫了兩個代碼，也都WA，感覺都沒錯，但結果卻WA 回復更多評論
# re: [動態規劃]pku1141
wobat
Posted @ 2008-07-01 16:27
對空的輸入，要輸出回車。。
也缺了#include<string>。。
其他的都對了回復更多評論
# re: [動態規劃]pku1141
wwq
Posted @ 2012-07-06 17:34
你的這個代碼提交WA了回復更多評論

刷新評論列表

只有注冊用戶登錄后才能發表評論。


相關文章: [動態規劃]O(n^2 / logn)的LCS [動態規劃] pku1458 最長公共子序列 [動態規劃]pku1080 [動態規劃]pku1338 [動態規劃]pku3420 [動態規劃]pku1191 [動態規劃]pku1179 [動態規劃]pku1189 [動態規劃]pku1185 [動態規劃]pku1163

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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

導航

常用鏈接

留言簿(22)

隨筆分類(145)

隨筆檔案(149)

相冊

ACMers

Pretty Girls

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜