牛客每日一题3月

目录：

3.26 NC13230.合并回文子串(区间DP)

3.27 NC15553.数学考试(线性DP)

NC13230.合并回文子串(区间DP)

题意：

给两个字符串a,b，你需要将两个字符串合并，并且保证新字符串中原来字符串的相对位置不变，求合并之后字符串最长回文子序列的长度

思路：

首先，先要了解一下如果求一个字符串的最长回文子序列问题这也是一个经典的区间DP问题

我们知道回文串是个左右对称的结构，所以一个回文串的增加长度是通过左右两边各加一个相同字母来实现的

所以，我们倾向于把子问题描述成：“字符串 s 的第 i 个字符到第 j 个字符的最长回文子序列长度”，

那么我们就用dp数组来表示它——dp[i][j为字符串 s 的第 i 个字符到第 j 个字符的最长回文子序列长度。

那么如何进行转移呢，可以看到字符串在向两端拓展时，会遇到以下两种情况

①s[i] == s[j]：这个时候可以把s[i]和s[j]分别加到原来0的回文子序列的两端，也就是 i+1 到 j-1 这个区间的字符构成的最长回文子序列的两端，此时 dp[i][j]=dp[i+1][j−1]+2

②s[i] != s[j]：那么在 i 到 j 这个区间的最长回文子序列中第 i 个字符和第 j 个字符一定不能同时存在，所以是可以扔掉他俩中的某一个的（并不是任意一个），此时 dp[i][j]=max(dp[i+1][j],dp[i][j−1])

之后就可以回到原来的问题了

我们定义dp[i][j][k][l]为表示前一个串（a串）的第 i 个字符到第 j 个字符后一个串（b串）的第 k 个字符到第 l 个字符能否组成一个回文串的话，有四种可能，四种当中任意一种为真f[i][j][k][l]就是真。

①往 a[i+1] 到 a[j−1] 和 b[k] 到 b[l] 构成的串的两端加上 a[i] 和 a[j] 两个字符：f[i][j][k][l]∣=(f[i+1][j−1][k][l]&(a[i]==a[j]));

②往 a[i+1] 到 a[j] 和 b[k] 到 b[l−1] 构成的串的两端加上 a[i] 和 b[l−1] 两个字符：f[i][j][k][l]∣=(f[i+1][j][k][l−1]&(a[i]==b[l]));

③往 a[i] 到 a[j−1] 和 b[k+1] 到 b[l]构成的串的两端加上 b[k] 和 a[j] 两个字符：f[i][j][k][l]∣=(f[i][j−1][k+1][l]&(b[k]==a[j]));

④往 a[i] 到 a[j] 和 b[k+1] 到 b[l−1] 构成的串的两端加上 b[k] 和 b[l−1] 两个字符： f[i][j][k][l]∣=(f[i][j][k+1][l−1]&(b[k]==b[l]));

问题解决，其实我们可以看到，这个朴素的最长回文子串问题并没有实质上的区别，只是首尾两端加字母的选择从原来的一种变成了2*2种。

一个小问题可能出现在边界上：f[i][i][k][k]的真假性显而易见的等于a[i]==b[k] 的真假性，但是转移过程中有可能找 a/b 串中有一个串一个字符都没有选的情况去转移

这个处理非常简单：只要两个串选中的字符个数等于1，直接f值等于1就好（果选中的字符个数小于1，那已经是非法状态了）

#include<iostream>
#include<algorithm>
#include<cstring>
 using namespace std;
 const int maxn=55;
 int dp[maxn][maxn][maxn][maxn];
 char a[maxn],b[maxn];
 int main()
 {
    int t;
    scanf("%d",&t);
    while(t--){
        memset(dp,0,sizeof(dp));
        scanf("%s%s",a+1,b+1);
        int n1=strlen(a+1),n2=strlen(b+1),ans=0;
        for(int len1=0;len1<=n1;len1++){
            for(int len2=0;len2<=n2;len2++){
                for(int i=1;i+len1-1<=n1;i++){
                    for(int k=1;k+len2-1<=n2;k++){
                        int j=i+len1-1,l=k+len2-1;//区间右端点 
                        if(len1+len2<=1)
                            dp[i][j][k][l]=1;//如果长度为1的话肯定为回文 
                        else{
                            if(len1>1) dp[i][j][k][l]|=(dp[i+1][j-1][k][l]&&(a[i]==a[j]));
                            if(len1&&len2) dp[i][j][k][l]|=(dp[i+1][j][k][l-1]&&(a[i]==b[l]));
                            if(len1&&len2) dp[i][j][k][l]|=(dp[i][j-1][k+1][l]&&(a[j]==b[k]));
                            if(len2>1) dp[i][j][k][l]|=(dp[i][j][k+1][l-1]&&(b[k]==b[l]));     
                        }
                        if(dp[i][j][k][l]) ans=max(len1+len2,ans); 
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
 }

NC15553.数学考试(线性DP)

题意：

给一个长度为n的数组，求在数组中求出两个不相交且长度为k的最大子段和

思路：

可以先预处理出一个前缀和sum[i]=a[1]+a[2]+..a[i],方便直接计算任意子段的和

之后定义dp[i]为从1到i中以i为终点的长度为k的最大子段和，所以dp[i]仅在i≥k时有定义

最后我们可以通过循环遍历，不断更新dp[i]，并且在i≥2k之后开始记录答案，ans=max(dp[i-k]+sum[i]-sum[i-k],ans)

要注意初始化答案与dp[i]为负无穷

#include<iostream>
#include<algorithm>
#include<cstring>
 using namespace std;
 const int maxn=2e5+10;
 typedef long long ll;
 ll dp[maxn],sum[maxn],a[maxn];
 int main()
 {
     int t,n,k;
     scanf("%d",&t);
     while(t--){
         scanf("%d%d",&n,&k);
         ll ans=-1ll<<60;
         for(int i=1;i<=n;i++){
             scanf("%lld",&a[i]);
             sum[i]=a[i]+sum[i-1];
             dp[i]=-1ll<<60;
         } 
        for(int i=k;i<=n;i++){
            dp[i]=max(dp[i-1],sum[i]-sum[i-k]);
            if(i>=2*k){
                ans=max(sum[i]-sum[i-k]+dp[i-k],ans);
            }        
        }
        cout<<ans<<endl;
     }
    return 0;
 }

几个变形的相关问题：
一：不限制长度——在一个数列里找两个不相交区间使得他们权值和最大

口胡思路:定义dp[i][0]为前i个数取0段，dp[i][1]为前k个数取1段，dp[i][2]为前k个数取2段

　　　　 那么状态转移方程式就为:dp[i][1]=max(dp[i][1],dp[i-1][0]+a[i])    开始选择第一段

　　　　　　　　　　　　　　　  dp[i][1]=max(dp[i][1],dp[i-1][1]+a[i])  在第一段中继续加数　

　　　　　　　　　　　　　　　  dp[i][2]=max(dp[i][2],max(dp[1.....i-1][1]+a[i])　开始选择第二段

　　　　　　　　　　　　　　　  dp[i][2]=max(dp[i][2],dp[i-1][2]+a[i])  在第二段中继续加数
二：区间数目变多——找m个长度为 k 的不相交区间使得他们的权值和最大 (1≤n≤5000)

口胡思路:定义dp[i][m]为前i个数中截取m个长度为k的段落的最大值

　　　　 那么状态转移方程式为dp[i][j]=max(dp[i-k][j]+sum[i]-sum[i-k],dp[i-1][k]) i>=j*k
三：区间数目变多且不限制长度——找 m 个不相交长度不限的区间使得他们权值和最大(1≤n≤5000)

口胡思路：有一道一模一样的题:https://vjudge.net/problem/HDU-1024

　　　　   dp[i][j]表示的是第j个数字在第i个子序列时的当前最优值。

　　　　　dp[i][j] = max(dp[i][j-1] + num[j] ,maxx(dp[i-1][k]) + num[j]);  1 ≤ k ≤ j-1

　　　　　可以这么理解这个转移方程，对于当前的这个数字，如果把他放到第i个子序列中有两种情况，一个是他作为第i个子序列的第一个数字，另一个就是不作为第一个数字

　　　　　作为第一个数字的时候是 max(dp[i-1][k] + num[j]) 1 ≤ k < i 的意思是从之前的所有中找到i-1个子序列的最大值+当前的值，不做为第一个的时候那么他前面的那个数字一定是i序列的，同一个子序

列，又不是作为第一个，那么前面的那个货就一定是同一个子序列的，那么当前的值是dp[i][j-1] + num[j],在两种决策中选择一个最有的就行了

还可以进行空间上的优化:如果m很大，那么状态转移就边成这样了dp[j]表示的是 j这个人在当前的这个子序列中的最优值，mk[j]表示的是在上一个子序列中1--j的dp的最大值，所以就变成 dp[j] = max(dp[j-1] + num[j],mk[j-1]+num[j]);还是 max(作为i个子序列的第一个元素，不是第一个元素取一个最大值)

#include <iostream>
#include<cstdio>
#include<cstring> 
#include<algorithm> 
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1000005;
int a[maxn],dp[maxn],pre[maxn];
int main()
{
    int m,n,tmp;
    while(scanf("%d%d",&m,&n)!=EOF){
        int tmp;
        for(int i=1;i<=n;++i) scanf("%d",&a[i]);
        memset(dp,0,sizeof(dp));
        memset(pre,0,sizeof(pre));
        for(int i=1;i<=m;++i){
            tmp=-inf;
            for(int j=i;j<=n;++j){
                dp[j]=max(dp[j-1],pre[j-1])+a[j];
                pre[j-1]=tmp;
                tmp=max(tmp,dp[j]);
            }
        }
        printf("%d
",tmp);
    }
    return 0;
}