HDU 4681 string 求最长公共子序列的简单DP+暴力枚举

先预处理,用求最长公共子序列的DP顺着处理一遍,再逆着处理一遍。

再预处理串a和b中包含串c的子序列,当然,为了使这子序列尽可能短,会以c 串的第一个字符开始 ,c 串的最后一个字符结束

将这些起始位置先记录下来,然后枚举这些位置,最大的值输出,看一下代码,你就会顿悟了····哈哈。

贴代码:

 #include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1005
using namespace std;
char a[][N],b[N];//a[0]为串a,a[1]为串b,b为串c
int dp1[N][N],dp2[N][N];
int len[],num[];//len[2]为串c的长度
struct node
{
int s,e;
} p[][N];
void init()//dp顺序,逆序求一次最长公共子序列
{
for(int i=; i<=len[]+; ++i)
{
dp1[][i] = ;
dp2[len[]+][i]=;
}
for(int i=; i<=len[]+; ++i)
{
dp1[i][] = ;
dp2[i][len[]+] =;
}
for(int i=; i<=len[]; ++i)
{
for(int j=; j<=len[]; ++j)
{
if(a[][i] == a[][j] ) dp1[i][j] = dp1[i-][j-]+;
else dp1[i][j] = max(dp1[i-][j],dp1[i][j-]);
}
}
for(int i=len[]; i>=; --i)
{
for(int j=len[]; j>=; --j)
{
if(a[][i]==a[][j]) dp2[i][j]=dp2[i+][j+]+;
else dp2[i][j] = max(dp2[i+][j],dp2[i][j+]);
}
}
}
//从串中找一个包含c串的以c[0]为开始,以c[len-1]为结束的一段,记录下起始位置
int pipei(int ind,int start)
{
int i,j=;
for(i=start+; i<=len[ind]; ++i)
{
if(a[ind][i] == b[j]) ++j;
if(j==len[]) break;
}
if(j <len[]) return -;
else return i;
}
//预处理出a串和b串中所有如上所述的子串的起始位置
void yumeiju(int ind)
{
num[ind] = ;
for(int i=; i<=len[ind]; ++i)
{
if(a[ind][i] == b[])
{
int e = pipei(ind,i);
if(e == -) continue;
p[ind][num[ind]].s=i;
p[ind][num[ind]].e = e;
++num[ind];
}
}
}
//枚举所有的可能,求解
int meiju()
{
init();
yumeiju();
yumeiju();
int ans=;
for(int i=; i<num[]; ++i)
{
for(int j=; j<num[]; ++j)
{
if(dp1[p[][i].s-][p[][j].s-] + dp2[p[][i].e+][p[][j].e+] > ans)
ans = dp1[p[][i].s-][p[][j].s-] + dp2[p[][i].e+][p[][j].e+] ;
}
}
return ans +len[];
}
int main()
{
// freopen("in.txt","r",stdin);
int t;
scanf("%d",&t);
a[][]='#';
a[][] ='#';
for(int ser =; ser<=t; ++ser)
{
scanf("%s%s%s",a[]+,a[]+,b);
len[]= strlen(a[])-;
len[] = strlen(a[])-;
len[] = strlen(b);
printf("Case #%d: %d\n",ser,meiju());
}
return ;
}
上一篇:Python:Selenium+Webdriver安装


下一篇:23.Linux-块设备驱动(详解)