洛谷动态规划2题 P1006&&P1140

P1006 传纸条

题目大意：（简化）一个n*m的矩阵，每一个点对应一个权值。要求你找出两条互不相交的路径从(1,1)出发到右下角(n,m)，问两条路径经过点的最大权值之和。

题目思路：

~~这好像是紫书上原题...，不过紫书上是个图~~

看一下这个题，如果把两条路径去掉，就是一个非常简单简单的dp。

那么从这个点出发，题目要求两条路径互不相交，那么可以维护两条路径，即一个四维dp。

设dp[i][k][j][l]代表第一张纸条传到 (i,k)，第二张纸条传到 (j,l) 时可以获得最大权值之和。

对于每一个状态(i,k),(j,l)就会有四种情况:

1.第一张纸条向下传递，第二张纸条向下传递

2.第一张纸条向下传递，第二张纸条向右传递

3.第一张纸条向右传递，第二张纸条向下传递

4.第一张纸条向右传递，第二张纸条向右传递

所以每一个状态会由之前的四个状态得出，但是会有重复情况，比如说第一张纸条向下传到 (i,k) 第二张纸条向下传到(j,l) ，这个时候我们维护的两个路径就相交了！！所以我们减去重复的部分mp[i][k]（该交点的权值）,意思就是我们让一条路径经过该点时得到的权值是0，那么该条路径就没经过这个点呗。

所以根据这四个状态再加一个去重即可得到代码：

#include <bits/stdc++.h>
#include<stdio.h>
#include <string.h>
#include<algorithm>
#pragma GCC optimize(2)
typedef long long ll;
const ll mod=9973;
const int maxn=5e2+5;
const ll INF=100000000000005;
using namespace std;
ll n,m;
ll mp[maxn][maxn];
ll dp[55][55][55][55];
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
        for(int k=1;k<=m;k++)
            scanf("%lld",&mp[i][k]);
    for(int i=1;i<=n;i++)
        for(int k=1;k<=m;k++)
            for(int j=1;j<=n;j++)
                for(int l=1;l<=m;l++){
                    dp[i][k][j][l]=max(dp[i][k][j][l],dp[i-1][k][j-1][l]+mp[i][k]+mp[j][l]);//down down
                    dp[i][k][j][l]=max(dp[i][k][j][l],dp[i-1][k][j][l-1]+mp[i][k]+mp[j][l]);//down right
                    dp[i][k][j][l]=max(dp[i][k][j][l],dp[i][k-1][j][l-1]+mp[i][k]+mp[j][l]);//right right
                    dp[i][k][j][l]=max(dp[i][k][j][l],dp[i][k-1][j-1][l]+mp[i][k]+mp[j][l]);//right down
                    if(i==j&&k==l) dp[i][k][j][l]-=mp[i][k];
                }
    printf("%lld\n",dp[n][m][n][m]);
}
/***
4 2 1
1 5 6 4
***/

P1140

题目大意：有两个字符串S与T，在每个字符串中可以加入‘-’(即题目中的空碱基)之后可以得到新的序列，问如何加入'-'构造出新序列之后，权值匹配之和最大。权值匹配满足下表：

题目思路：

首先第一波操作没有疑问应该是直接建表找出对应关系

然后分析，应该是个dp题。

类比最长公共子序列的dp。

我们设dp[i][k]代表我们用S的i个字符与T的j个字符匹配可以产生的最大权值

有以下三种状态：

1.第一个字符串的第i个碱基匹配空碱基

2.第二个字符串的第j个碱基匹配空碱基

3.第一个字符串的第i个碱基匹配第二个字符串的第j个碱基匹配

所以每个点都可以由三个状态转移而来，然后注意一下边界问题：即第一个字符串第0个碱基与第二个字符串所有碱基匹配，很容易看出，这个时候只能让第二个字符串匹配空碱基，所以他的来源只有一个状态。同样的第二个字符串的0个碱基匹配也是如此。

得出三个状态+一个边界状态得到本题AC代码：

#include <bits/stdc++.h>
#include<stdio.h>
#include <string.h>
#include<algorithm>
#pragma GCC optimize(2)
typedef long long ll;
const ll mod=9973;
const int maxn=5e2+5;
const ll INF=100000000000005;
using namespace std;
ll n,m;
ll dp[maxn][maxn],cop[maxn];
char s1[maxn],s2[maxn];
int a[maxn],b[maxn];
ll ta[5][5]={
    {5ll,-1ll,-2ll,-1ll,-3ll},
    {-1ll,5ll,-3ll,-2ll,-4ll},
    {-2ll,-3ll,5ll,-2ll,-2ll},
    {-1ll,-2ll,-2ll,5ll,-1ll},
    {-3ll,-4ll,-2ll,-1ll,0ll}
};
void restart()
{
    for(int i=1;i<=n;i++) {
        if(s1[i]=='A') a[i]=0;
        if(s1[i]=='C') a[i]=1;
        if(s1[i]=='G') a[i]=2;
        if(s1[i]=='T') a[i]=3;
        if(s1[i]=='-') a[i]=4;
    }
    for(int i=1;i<=m;i++) {
        if(s2[i]=='A') b[i]=0;
        if(s2[i]=='C') b[i]=1;
        if(s2[i]=='G') b[i]=2;
        if(s2[i]=='T') b[i]=3;
        if(s2[i]=='-') b[i]=4;
    }
}
int main()
{
    scanf("%lld%s%lld%s",&n,s1+1,&m,s2+1);
    restart();
    for(int i=1;i<=n;i++)
        for(int k=1;k<=m;k++) 
            dp[i][k]=-INF;
    for(int i=1;i<=n;i++) dp[i][0]=dp[i-1][0]+ta[a[i]][4];
    for(int i=1;i<=m;i++) dp[0][i]=dp[0][i-1]+ta[4][b[i]];
    for(int i=1;i<=n;i++){
        for(int k=1;k<=m;k++){
            dp[i][k]=max(dp[i][k],dp[i-1][k-1]+ta[a[i]][b[k]]);
            dp[i][k]=max(dp[i][k],dp[i-1][k]+ta[a[i]][4]);
            dp[i][k]=max(dp[i][k],dp[i][k-1]+ta[4][b[k]]);
        }
    }
    printf("%lld\n",dp[n][m]);
}
/***
4 2 1
1 5 6 4
***/