括弧マッチ(二)
11618 ワード
テーマリンク:http://acm.nyist.net/JudgeOnline/problem.php?pid=15
考え方:ダイナミック企画
二次元配列dpを使用して中間結果を保存し、dp[i][j]は括弧サブシーケンスs[i]s[i＋1]...s[j]が正確に補完すべき最小括弧数(以下、N(i,j)という)を保存しています.
サブシーケンス長が1の場合、すなわち(、)、［、］の4つの場合、N=1.すなわちdp[i]、[i]=1.
サブシーケンス長がnの場合(s［i］s［i＋1］…s［j］、j−i＋1=n)、N(i,j)はセットSの最小値となる.
集合Sの構造過程:
0)Sを空セットにする
1)N(i＋1、j−1)は、(s[i]=')または(s[i]='('、s[j]=')')の場合、Sに加入する.
具体的には、i＋1=jの場合(s[i]s[j]が[]]または()]の場合)は、i＋1>j-1であり、(i＋1)-(j-1)=1であるため、前処理の際にはdp[i]、[i-1]=0が必要となる.
2)N(i,k)＋N(k,j)をSに加入し(i≦k≦j)、s[i]...s[j]を2つのサブストリングに分割し、2つのサブストリングのNを加算するとs[i]...s[j]が取り得る1つのN値となる.
Sの計算は、長さ1,2…n−1のs［i］…s［j］のサブシーケンスN値を使用する.
nの増加に伴い、dpの値も反復的に更新され、サブシーケンスがs全体に成長すると、出力dp[1]、[s.length]はsの最小N値である.
参照コード(ソース:http://hi.baidu.com/3bian/blog/item/56adfa3f17024ef4828b13d8.html):
考え方:ダイナミック企画
二次元配列dpを使用して中間結果を保存し、dp[i][j]は括弧サブシーケンスs[i]s[i＋1]...s[j]が正確に補完すべき最小括弧数(以下、N(i,j)という)を保存しています.
サブシーケンス長が1の場合、すなわち(、)、［、］の4つの場合、N=1.すなわちdp[i]、[i]=1.
サブシーケンス長がnの場合(s［i］s［i＋1］…s［j］、j−i＋1=n)、N(i,j)はセットSの最小値となる.
集合Sの構造過程:
0)Sを空セットにする
1)N(i＋1、j−1)は、(s[i]=')または(s[i]='('、s[j]=')')の場合、Sに加入する.
具体的には、i＋1=jの場合(s[i]s[j]が[]]または()]の場合)は、i＋1>j-1であり、(i＋1)-(j-1)=1であるため、前処理の際にはdp[i]、[i-1]=0が必要となる.
2)N(i,k)＋N(k,j)をSに加入し(i≦k≦j)、s[i]...s[j]を2つのサブストリングに分割し、2つのサブストリングのNを加算するとs[i]...s[j]が取り得る1つのN値となる.
Sの計算は、長さ1,2…n−1のs［i］…s［j］のサブシーケンスN値を使用する.
nの増加に伴い、dpの値も反復的に更新され、サブシーケンスがs全体に成長すると、出力dp[1]、[s.length]はsの最小N値である.
参照コード(ソース:http://hi.baidu.com/3bian/blog/item/56adfa3f17024ef4828b13d8.html):
#include
<
iostream
>
#include
<
string
>
#include
<
climits
>
using
namespace
std;
const
int
MAX
=
100
;
int
dp[MAX][MAX];
int
main()
{
int
n;
cin
>>
n;
while
(n
--
){
string
s;
cin
>>
s;
int
n
=
s.length();
for
(
int
i
=
1
;i
<=
n;i
++
)
dp[i][i
-
1
]
=
0
;
for
(
int
i
=
1
;i
<=
n;i
++
)
dp[i][i]
=
1
;
for
(
int
k
=
1
;k
<=
n
-
1
;k
++
)
//
k =
{
for
(
int
i
=
1
;i
<=
n
-
k;i
++
)
//
i = （ ）
{
int
j
=
i
+
k;
//
j = （ ）
dp[i][j]
=
INT_MAX;
if
(s[i
-
1
]
==
'
(
'
&&
s[j
-
1
]
==
'
)
'
||
s[i
-
1
]
==
'
[
'
&&
s[j
-
1
]
==
'
]
'
)
dp[i][j]
=
dp[i
+
1
][j
-
1
];
for
(
int
p
=
i;p
<
j;p
++
)
{
if
(dp[i][p]
+
dp[p
+
1
][j]
<
dp[i][j]) dp[i][j]
=
dp[i][p]
+
dp[p
+
1
][j];
}
}
}
cout
<<
dp[
1
][s.length()]
<<
endl;
}
return
0
;
}