2018.07.09 顺序对齐(线性dp)
顺序对齐
题目描述
考虑两个字符串右对齐的最佳解法。例如,有一个右对齐方案中字符串是 AADDEFGGHC 和 ADCDEGH。
AAD~DEFGGHC
ADCDE~~GH~
每一个数值匹配的位置值 2 分,一段连续的空格值 -1 分。所以总分是匹配点的 2 倍减去连续空格的段数,在上述给定的例子中,6 个位置 (A,D,D,E,G,H) 匹配,三段空格,所以得分 2*6+(-1)*3=9,注意,我们并不处罚左边的不匹配位置。若匹配的位置是两个不同的字符,则既不得分也不失分。
请你写个程序找出最佳右对齐方案。
输入格式
输入文件包含两行,每行一个字符串,最长 50 个字符。字符全部是大字字母。
输出格式
输出一个整数,为最佳对齐的得分。
样例数据 1
输入
AADDEFGGHC
ADCDEGH
输出
9
一道一眼题,一看就是基础dp" role="presentation" style="position: relative;">dpdp,设f[i][j]" role="presentation" style="position: relative;">f[i][j]f[i][j]表示a" role="presentation" style="position: relative;">aa串中第i" role="presentation" style="position: relative;">ii个跟b" role="presentation" style="position: relative;">bb串中第j" role="presentation" style="position: relative;">jj个匹配时收益最大值。这样状态转移方程就很显然了吧。我们知道两个字串在同样的位置出现空格是不优秀的。这样的话,f[i][j]" role="presentation" style="position: relative;">f[i][j]f[i][j]就只能由f[i−1][k]" role="presentation" style="position: relative;">f[i−1][k]f[i−1][k]和f[k][j−1]" role="presentation" style="position: relative;">f[k][j−1]f[k][j−1]推出来,最后统计答案就行了。
代码如下:
#include<bits/stdc++.h>
using namespace std;
char a[55],b[55];
int la,lb,f[55][55],ans=0;
int main(){
scanf("%s%s",a+1,b+1);
la=strlen(a+1),lb=strlen(b+1);
memset(f,0,sizeof(f));
for(int i=1;i<=la;++i)if(a[i]==b[1])f[i][1]=2;
for(int i=1;i<=lb;++i)if(a[1]==b[i])f[1][i]=2;
for(int i=2;i<=la;++i)
for(int j=2;j<=lb;++j){
f[i][j]=f[i-1][j-1];
for(int k=1;k<i-1;++k)f[i][j]=max(f[k][j-1]-1,f[i][j]);
for(int k=1;k<j-1;++k)f[i][j]=max(f[i-1][k]-1,f[i][j]);
f[i][j]+=2*(a[i]==b[j]);
}
for(int i=1;i<=la;++i)ans=max(ans,f[i][lb]-1*(i!=la));
for(int i=1;i<=lb;++i)ans=max(ans,f[la][i]-1*(i!=lb));
printf("%d",ans);
return 0;
}
最新文章
- Delphi多线程的OnTerminate属性(附加一个关于临界区线程同步的例子)
- JAVA-Excel文件操作
- 使用ConditionalScope进行高效的SharePoint CSOM编程
- RequestContextListener有什么用
- 华东交通大学2016年ACM“双基”程序设计竞赛 1001
- depthstencil buffer 不支持 msaa
- ArcEngine实现捕捉节点
- gcc/g++ 如何支持c11 / c++11标准编译
- POJ 2632 Crashing Robots (坑爹的模拟题)
- 《深入浅出MySQL》之SQL基础
- bootstrap学习(二)页面
- vue scrolle在tab 中使用
- 关于Struts2中 Action 配置method的解读
- nrf2401 - 最廉价的2.4G无线通信方案
- PHP on CentOS (LAMP) and wordpress
- LOJ6089 小Y的背包计数问题 背包、根号分治
- 继承数组的slice方法
- hive\hadoop 常用命令
- BUG的严重级别分类 BUG状态标准
- Bootstrap学习笔记-栅格系统