B. Catching Cheaters
对于我们做过的模板提来说
这道题是子串
那显然我们要改变一下我们的状态表示
dp[i][j]表示以ai,bj结尾的max
我们状态转移就是
dp[i][j]=max{dp[i-1][j-1]+2} [ai==bj]
dp[i][j]=max{dp[i-1][j]-1,dp[i][j-1]-1,dp[i][j]}
因为我们初始化就是0 所以要是负数我们直接就剪掉了
我们需要的只是传到下一个子段还有权值的段
#include <bits/stdc++.h>
using namespace std;
const int N = (1<<18)+10;
const int M = 998244353;
const int mod = 1e9+7;
#define int long long
int up(int a,int b){return a<0?a/b:(a+b-1)/b;}
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define YES cout<<"YES"<<endl;
#define NO cout<<"NO"<<endl;
#define _ 0
#define pi acos(-1)
#define INF 0x3f3f3f3f3f3f3f3f
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
int dp[5010][5010];
char a[5010],b[5010];
void solve(){
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)cin>>b[i];
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i]==b[j])dp[i][j]=max(dp[i-1][j-1]+2,dp[i][j]);
dp[i][j]=max(dp[i-1][j]-1,dp[i][j]);
dp[i][j]=max(dp[i][j-1]-1,dp[i][j]);
ans=max(ans,dp[i][j]);
}
}
cout<<ans<<endl;
}
signed main(){
fast
int t;t=1;//cin>>t;
while(t--) {
solve();
}
return ~~(0^_^0);
}
标签:int,max,Codeforces,bj,ai,Meet,Div,dp
From: https://www.cnblogs.com/ycllz/p/16844241.html