DP（关于字符串，数字串的）

1 dp关系

2 初始情况

3s 512M

【题目表述】

某天醒来，koishi发现自己变成了一支彩笔。并且他站在一排彩笔之中。

一开始每支彩笔的彩笔程度都为1。如果有两支彩笔颜色相同，那么他们就能合二为一，并且彩笔程度相加。

现在koishi想知道，从第l支彩笔到第r支彩笔，最多能有多大的彩笔程度。

【输入格式】

第一行为彩笔数量n和询问次数q
第二行为n个这个整数，每个整数代表这个彩笔的颜色
接下来q行，每行两个整数l和r

【输出格式】
共q行，每行一个整数，表示最大的彩笔程度

【样例输入】
6 2
1 3 2 3 3 2
1 6
2 4

【样例输出】
3
2

【数据范围与提示】
1<=n,q<=3*1e5
1<=彩笔颜色<=n
1<=l<=r<=n

对于样例的第一个询问，颜色为1的彩笔程度为1，颜色为2的彩笔程度为2，3的彩笔程度为3，因此彩笔程度最大为3。
对于第二个询问，颜色为2的彩笔程度为1，颜色为3的彩笔程度为2，因此彩笔程度最大为2。

#include 
using namespace std;
#define ri register int 
#define M 1005

template <class G>void read(G &x)
{
    x=0;int f=0;char ch=getchar();
    while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return ;
}

int a[M];
int b[M];
int f[M][M];
int n,m;
int main(){
    
    freopen("D:\\学习\\C++\\swjtu比赛\\2021校赛决赛文档\\极致美学\\data\\20.in","r",stdin);
    read(n);read(m);
    for(ri i=1;i<=n;i++)
    read(a[i]);
    for(ri i=1;i<=m;i++)
    read(b[i]);
    
    for(ri i=1;i<=max(n,m);i++) f[0][i]=f[i][0]=i;
    for(ri i=1;i<=n;i++)
    {
        for(ri j=1;j<=m;j++)
        {
            if(a[i]==b[j]) f[i][j]=f[i-1][j-1];
            else {
                f[i][j]=min(f[i][j-1],f[i-1][j])+1;
            }
            f[i][j]=min(f[i][j],f[i-1][j-1]+1);
        }
    }
    cout<<f[n][m];
    return 0;
    
}

好难啊。不是很想通

类似：

试题 算法提高 最长公共子序列
     
资源限制
时间限制：1.0s   内存限制：256.0MB
问题描述
　　给定两个字符串，寻找这两个字串之间的最长公共子序列。
输入格式
　　输入两行，分别包含一个字符串，仅含有小写字母。
输出格式
　　最长公共子序列的长度。
样例输入
abcdgh
aedfhb
样例输出
3
样例说明
　　最长公共子序列为a，d，h。
数据规模和约定
　　字串长度1~1000。

#include 
using namespace std;
#define ri register int
#define M 1005

template <class G>void read(G x)
{
    x=0;int f=0;char ch=getchar();
    while(ch<'0'||ch>'9'){f|=(ch=='-');ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
    return ;
}

int n;
string s1;
string s2;
int f[M][M];
int main(){
    
    cin>>s1;
    cin>>s2;
    int n=s1.length();
    int m=s2.length();
    for(ri i=1;i<=n;i++)
    for(ri j=1;j<=m;j++)
    {
        if(s1[i-1]==s2[j-1])
        {
            f[i][j]=f[i-1][j-1]+1;
            continue;
        }
        f[i][j]=max(f[i-1][j-1],f[i][j-1]);
        f[i][j]=max(f[i][j],f[i-1][j]);
    }
    
    cout<<f[n][m];
    return 0;
    
} 

注意 ： 数组的元素不能有负数，在 dp 的时候注意一下。