题解 洛谷P4059 线性dp

· · 个人记录

前言

可怜的 zsw 被暴捶力，只能开始恶补 dp 了。

比较抽象，只是给自己看的。

思路

题意自己看啊啊啊。

为了方便表述，称第一个串为 s1，第二个为 s2，字符串的下标从 1 开始。

看完后可以得知重要的一点：由于 A,B>0，所以有 -A-B(k-1) 随 k 增大单调递减。

所以同一行不可能出现两个空格，显然去掉它俩以后值更大。

那么有个初步思路，f_{i,j} 表示 s1[1,i] 与 s2[1,j] 的最大相似度。

然而你会发现根本做不了，因为相似度与每个元素的相对位置息息相关，但状态中根本没有涉及到相对位置，因此是个假做法。

for example，假设 f_{1,2} 所代表的两串长这样：

A** T*C

考虑将 i 拓展一位，那么该状态可以拓展至：

AT* T*C

可是若 f_{1,2} 是这样子的：

**A *TC

那么拓展状态是：

**AT *TC*

如上图所示，不同种类状态的拓展状态可能是不同的，只有二维的状态定义所带来的后果是毁灭性的。

不过这也带来启发，二维不行，加上一位就好了嘛。

对于所有空格，我们只关心末尾是否有空格，这不仅与 A,B 有关，还和可转移到的状态有关，因此定义：

来看看它是怎么解决上述问题的：前者被分类为 f_{1,2,1}，后者被分类为 f_{1,2,0}，只需在状态转移时规定好即可。

再解释下“与 A,B 有关” 是什么意思：容易想到，g(k) 等价于首个空格减去 A，此后连续的空格均是减去 B，而我们的状态刚好可以解决这个问题，考虑上个状态末尾的空格即可。

到此已经完成了 50\% 了。

转移方程：

代码

注意初始化，思路清晰了就很容易一遍过的。

#include<bits/stdc++.h>
using namespace std;

#define s1(i) (s1[i]=='A'?1:(s1[i]=='T'?2:(s1[i]=='G'?3:4)))
#define s2(i) (s2[i]=='A'?1:(s2[i]=='T'?2:(s2[i]=='G'?3:4)))
string s1,s2;
int n,m,val[5][5],A,B,f[3005][3005][3];

signed main(){
    cin>>s1>>s2;
    n=s1.size(); m=s2.size();
    s1=" "+s1; s2=" "+s2;
    for(int i=1; i<=4;i++)
     for(int j=1; j<=4;j++)
      cin>>val[i][j];
    cin>>A>>B;
    memset(f,-0x3f,sizeof f);
    for(int i=1; i<=n;i++) f[i][0][1]=-A-B*(i-1);
    for(int i=1; i<=m;i++) f[0][i][2]=-A-B*(i-1);
    f[0][0][0]=0;
    for(int i=1; i<=n;i++){
        for(int j=1; j<=m;j++){
            f[i][j][0]=val[s1(i)][s2(j)]+max(f[i-1][j-1][0],max(f[i-1][j-1][1],f[i-1][j-1][2]));
            f[i][j][1]=max(max(f[i-1][j][0],f[i-1][j][2])-A,f[i-1][j][1]-B);
            f[i][j][2]=max(max(f[i][j-1][0],f[i][j-1][1])-A,f[i][j-1][2]-B);
        }
    }
    cout<<max(f[n][m][0],max(f[n][m][1],f[n][m][2]));
    return 0;
}