欧美午夜精品久久久久久人妖 ,欧美激情一区二区三区四区,日韩一级在线

[動(dòng)態(tài)規(guī)劃]pku1141

int f[i][j]表示第i個(gè)字符到第j個(gè)字符需要添加的最少括號(hào)數(shù)。string ans[i][j] 表示第i個(gè)字符到第j個(gè)字符按照最優(yōu)方案添加括號(hào)后的串。狀態(tài)轉(zhuǎn)移：1.f[i][j]由f[i + 1][j - 1]轉(zhuǎn)移來(lái)（通過(guò)兩端添括號(hào)() / [] ）。2.f[i][j]由f[i][k] + f[k + 1][j]轉(zhuǎn)移來(lái)（通過(guò)串合并）。答案是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) 評(píng)論(3) 編輯收藏引用所屬分類: 動(dòng)態(tài)規(guī)劃

Comments

# re: [動(dòng)態(tài)規(guī)劃]pku1141
l-y-p
Posted @ 2008-03-03 11:36
你的這個(gè)代碼提交也WA，不知是怎么回事，自己也寫(xiě)了兩個(gè)代碼，也都WA，感覺(jué)都沒(méi)錯(cuò)，但結(jié)果卻WA 回復(fù) 更多評(píng)論
# re: [動(dòng)態(tài)規(guī)劃]pku1141
wobat
Posted @ 2008-07-01 16:27
對(duì)空的輸入，要輸出回車。。
也缺了#include<string>。。
其他的都對(duì)了回復(fù) 更多評(píng)論
# re: [動(dòng)態(tài)規(guī)劃]pku1141
wwq
Posted @ 2012-07-06 17:34
你的這個(gè)代碼提交WA了回復(fù) 更多評(píng)論

刷新評(píng)論列表

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。


相關(guān)文章: [動(dòng)態(tài)規(guī)劃]O(n^2 / logn)的LCS [動(dòng)態(tài)規(guī)劃] pku1458 最長(zhǎng)公共子序列 [動(dòng)態(tài)規(guī)劃]pku1080 [動(dòng)態(tài)規(guī)劃]pku1338 [動(dòng)態(tài)規(guī)劃]pku3420 [動(dòng)態(tài)規(guī)劃]pku1191 [動(dòng)態(tài)規(guī)劃]pku1179 [動(dòng)態(tài)規(guī)劃]pku1189 [動(dòng)態(tài)規(guī)劃]pku1185 [動(dòng)態(tài)規(guī)劃]pku1163

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理

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

導(dǎo)航

常用鏈接

留言簿(22)

隨筆分類(145)

隨筆檔案(149)

相冊(cè)

ACMers

Pretty Girls

最新隨筆

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜