题意
给定一个两个长度为5n的序列, 保证每个序列1-n各出现5次, 求最长公共子序列
\(n \leq 20000\)
题解
首先, 突破点肯定是每个数只出现5次。
然后我们开始思考这和普通lcs的区别在于: 能和每个数匹配的至多只有5个数
我们再看看朴素的lcs, 朴素的lcs设 \(f_{i, j}\) 表示到s到i, t到j的最长长度, 假如\(S_i == T_j\) 那么可以他们匹配。
但事实上: 我们可以假装没学过lcs, 那按照我一贯的dp手法, 一定会分阶段dp;
我们这样理解,fi,j表示s匹配到i, t匹配到j的最大长度,并且i, j一定要匹配起来的最大值
fi就表示我们现在要匹配si,那么我们可以用一个线段树来维护状态,
假如我们完全不匹配, 那么每一个状态就和fi-1,j相等,
这时候我们开始匹配, 对于5各点中的每一个点x, 我们让
瞎乱线段树维护一下
#include <iostream>
#include <cstdio>
#define ll long long
#define l(x) ((x)<<1)
#define r(x) (l(x)+1)
using namespace std;
const int N = 100005;s
int n, m, a[N];
ll tree[N<<2], tag[N<<2];
void push_up(int o){
tree[o] = tree[l(o)] + tree[r(o)];
}
void f(int o, int l, int r, int v){
tree[o] = 1ll*(r-l+1)*v;
tag[o] = v;
}
void push_down(int o, int l, int r){
int mid = (l+r)/2;
f(l(o), l, mid, tag[o]);
f(r(o), mid+1, r, tag[o]);
tag[o] = 0;
}
void build(int o, int l, int r){
if(l==r){
tree[o] = a[l];
return ;
}
int mid = (l+r)/2;
build(l(o), l, mid);
build(r(o), mid+1, r);
push_up(o);
}
ll query(int o, int l, int r ,int ql, int qr){
if(ql<=l&&r<=qr) return tree[o];
int mid=(l+r)/2;ll res=0;
push_down(o, l, r);
if(ql <= mid) res = query(l(o), l, mid, ql, qr);
if(qr > mid) res = max(res, )query(r(o), mid+1, r, ql, qr));
return res;
}
void update(int o, int l, int r, int ql, int qr, int v){
if(ql<=l&&r<=qr){
f(o, l, r, v);
return ;
}
int mid = (l+r)/2;
push_down(o, l, r);
if(ql<=mid) update(l(o), l, mid, ql, qr, v);
if(qr>mid) update(r(o), mid+1, r, ql, qr, v);
push_up(o);
}
ll query(int l, int r){
return query(1, 1, n, l, r);
}
ll update(int l, int r, int v){
update(1, 1, n, l, r, v);
}
int read(){
int num=0, flag=1; char c=-1;
while((c<'0' || c>'9')&&c!='-') c=getchar();
if(c=='-') flag=-1, c=getchar();
while(c>='0' && c<='9') num=num*10+c-'0', c=getchar();
return num*flag;
}
int s[N], t[N], p[N][10];
void scan(){
n=read()*5;
for(int i=1; i<=n; i++){
a[i] = 0;
}
build(1, 1, n);
for(int i=1; i<=n; i++){
s[i] = read();
}
for(int i=1; i<=n; i++){
t[i] = read();
for(int j=1; j<=5; j++){
if(!p[t[i]][j]){
p[t[i]][j] = i;
}
}
}
}
void solve(){
}
int main(){
scan();
solve();
return 0;
}
什么东西啊, 我自己都看不懂