本文主要是介绍poj 2955(区间DP)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
| Language: Brackets
Description We give the following inductive definition of a “regular brackets” sequence:
For instance, all of the following character sequences are regular brackets sequences:
while the following character sequences are not:
Given a brackets sequence of characters a1a2 … an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i1,i2, …, im where 1 ≤ i1 < i2 < … < im ≤ n, ai1ai2 … aim is a regular brackets sequence. Given the initial sequence Input The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters Output For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line. Sample Input ((()))()()()([]]))[)(([][][)end Sample Output 66406 |
题解:
题意：在一些括号中找到一个序列，里面的括号都两两配对。求序列最长长度。
区间DP，dp[i][j]为i~j的最大括号数，考虑第i个括号，有两种情况：
1.不管i直接算dp[i + 1][j];
2.找到和i匹配的右括号，分两边算并加起来.dp[i][j] = dp[i + 1][k - 1] + 2 + dp[k + 1][j]。
我在这里就吃了一个大亏:我一直认为只有s[i]不为"("和"["时候才匹配第一种情况,
其实不是,考虑这种情况"([]",当s[i]等于'('时候,依旧要在第一种和第二种情况中取最大的.
综合一下就是无论什么情况,都要算第一种和第二种而且是取他们中最大的.
这是我的错误程序,留作纪念:这里的重点是添加了一个自动测试语句,检测正确的程序和我的程序在那个用例上输出不一致.
#include <iostream>
#include <string>
#include <time.h>
using namespace std;
#define Max 300
int dp[Max][Max];
int dp123[205][205];//表示从i到j的最大匹配。
bool match(int i,int j,const string &str)
{
if((str[i]=='('&&str[j]==')')||(str[i]=='['&&str[j]==']'))
return true;
else return false;
}
int maxi(int a,int b)
{
if(a>b)
return a;
else return b;
}
int dpf(const string &str)
{
int i,j,k,len,g;
/* if(str[0]=='e'&&str[1]=='n'&&str[2]=='d')
return 0;*/
memset(dp123,0,sizeof(dp123));
len=str.size();
for(i=1;i<len;i++)
{//初始化从i到i+1这个的dp
if(match(i-1,i,str)==true)
dp123[i][i+1]=1;
}
for(i=3;i<=len;i++)
for(j=1;j<=len-i+1;j++)
{
k=j+i-1;
//这一步是必须得，这个相当于是最后一个和第一个匹配，然后找中间的最大匹配
//这个状态下面的for覆盖不了，必须单独判断一下
if(match(j-1,k-1,str)==true)
dp123[j][k]=dp123[j+1][k-1]+1;
//这个相当于是从j开始找到一个位置的最大匹配加上从这个位置到k的最大匹配
//有点分治法的味道。
for(g=0;g<k;g++)
dp123[j][k]=maxi(dp123[j][k],dp123[j][j+g]+dp123[j+g+1][k]);
}
return dp123[1][len]*2;
}
int dpfunc(const string &s){
memset(dp,0,sizeof(dp));
int len = s.length();
if (len==0) return 0;
for ( int step=1; step<len; ++step ){
for (int i=0; i<len-step; ++i ) {
if ( s[i]!='(' && s[i]!='[' ) {
dp[i][i+step] = dp[i+1][i+step];
continue;
}
int max =0;
for ( int k=i+1,j=i+step; k<=j; ++k ){
if (!((s[i]=='(' && s[k]==')') ||(s[i]=='[' && s[k]==']'))) continue;
int temp = dp[i+1][k-1]+dp[k+1][j]+2;//在这里k有可能大于j,由于当k>j时候dp全部为0,所以也会成立
max = max >temp ? max : temp;
}
dp[i][i+step] = max;
}
}
return dp[0][len-1];
}
int main()
{
char ch[4]={'[',']','(',')'};
srand( (unsigned)time( NULL ) );
char c[50];
int len = rand()%50;
// cin>>s;
while (true){
for ( int i=0; i<len; ++i ){
int index = rand()%4;
c[i]=ch[index];
}
c[len]= '\0';
string s(c);
if(s[0]=='e'&&s[1]=='n'&&s[2]=='d')
break;
//cout<<dpfunc(s)<<endl;
if (dpfunc(s)!=dpf(s)){
cout<<s<<endl;
cout<<dpfunc(s)<<" "<<dpf(s)<<endl;
break;
}
}
return 0;
}ac的程序:
#include <iostream>
#include <string>
#include <time.h>
using namespace std;
#define Max 300
int dp[Max][Max];
int dpfunc(const string &s){
memset(dp,0,sizeof(dp));
int len = s.length();
if (len==0) return 0;
for ( int step=1; step<len; ++step ){
for (int i=0; i<len-step; ++i ) {
int max = dp[i+1][i+step];
for ( int k=i+1,j=i+step; k<=j; ++k ){
if (!((s[i]=='(' && s[k]==')') ||(s[i]=='[' && s[k]==']'))) continue;
int temp = dp[i+1][k-1]+dp[k+1][j]+2;//在这里k有可能大于j,由于当k>j时候dp全部为0,所以也会成立
max = max >temp ? max : temp;
}
dp[i][i+step] = max;
}
}
return dp[0][len-1];
}
int main()
{
string s;
cin>>s;
while (s!="end"){
cout<<dpfunc(s)<<endl;
cin>>s;
}
return 0;
}
这篇关于poj 2955(区间DP)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
