POJ 2995 Brackets 区间DP

POJ 2995 Brackets 区间DP

题意

大意:给你一个字符串,询问这个字符串满足要求的有多少,()和[]都是一个匹配。需要注意的是这里的匹配规则。

解题思路

区间DP,开始自己没想到是区间DP,以为就是用栈进行模拟呢,可是发现就是不大对,后来想到是不是使用DP,但是开始的时候自己没有推出递推关系,后来实在想不出来看的题解,才知道是区间DP,仔细一想确实是啊。

下面就是状态转移方程:

\[\begin{cases}dp[i][j] &=& dp[i+1][j-1]+if(str[i]和str[j]匹配) \\dp[i][j] &=& dp[i][k]+dp[k+1][j] & k=i+1,i+2,………j-1\end{cases}
\]

当初知道了转移方程,就自己写代码,可是就是不对,下面有两个代码,一个是错误的,一个是正确的,两个对比看一看原因。

代码实现

//这个是正确的
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e3+7;
char str[maxn];
int dp[maxn][maxn];
int main()
{
while(scanf("%s", &str))
{
if(strcmp("end", str)==0)
break;
int n=strlen(str);
memset(dp, 0, sizeof(dp));
//下面书写的格式很重要,先算长度为1的区间,然后再算区间为2的区间,以此类推
for(int len=1; len<=n; len++)
{
for(int L=0; L+len<n; L++)
{
int R=L+len;
if((str[L]=='(' && str[R]==')') || (str[L]=='[' && str[R]==']'))
{
dp[L][R]=dp[L+1][R-1]+2;
}
for(int k=L; k<R; k++)
{
dp[L][R]=max(dp[L][R], dp[L][k]+dp[k+1][R]);
}
}
}
printf("%d\n", dp[0][n-1]);
}
return 0;
}
//这个是错误的代码,下面分析主要原因,连样例都过不了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
stack<char> st;
const int maxn=1e4+7;
char str[maxn];
int dp[maxn][maxn];
int main()
{
while(scanf("%s", str))
{
if(strcmp("end", str)==0)
break;
int n=strlen(str);
memset(dp, 0, sizeof(dp));
//下面的代码其实是有点问题的,应该是先算长度全为1的区间段,然后再是长度为2的,以此类推
//为什么要这这样呢,因为下面的max函数中第二项是一个重要的部分
for(int L=0; L<len; L++)
{
for(int R=i+1; R<len; R++)
{
dp[L][R]=dp[L+1][R-1];
if(str[L]=='(' && str[R]==')' || str[L]=='[' && str[R]==']')
{
dp[L][R]+=2;
}
for(int k=L; k<R; k++)
{
//下面的后两项之和应该在计算dp[L][R]之前就应该计算了,但是这里可能没有。
//所以区间DP的书写格式还是有点套路的。
dp[L][R]=max(dp[L][R], dp[L][k]+dp[k+1][R]);
}
}
}
printf("%d\n", dp[0][len-1]);
}
return 0;
}
上一篇:mysql数据类型优化


下一篇:poj 3734 Blocks 快速幂+费马小定理+组合数学