2021.12.10 P2516 [HAOI2010]最长公共子序列(动态规划+滚动数组)

2021.12.10 P2516 [HAOI2010]最长公共子序列(动态规划+滚动数组)

https://www.luogu.com.cn/problem/P2516

题意:

给定字符串 \(S\) 、 \(T\) ,都以 \(.\) 结尾,求 \(S\) 、 \(T\) 最长公共子序列的长度及个数。

分析:

一顿操作猛如虎,一看分数250……爆零了。原本就没准备拿几分,结果令人心塞。

第一问就是求最长公共子序列长度,数据范围比较小, \(O(n^2)\) 就行,上来就是一顿树状数组+LIS,忽视了里面有重复出现的字符。正解就是普普通通的DP,啥也没加,因为也加不了啥。

第二问实际上是第一问的深入思考(大雾)。

先来看求LCS的状态转移方程:

\[f[i][j]=\begin{cases} f[i-1][j-1]+1,&S_i==T_j\\ \max(f[i][j-1],f[i-1][j]),&S_i!=T_j \end{cases} \]

对于第一个转移方程,相当于是 \(S\) 的前 \(i\) 个字符全部出现在LCS中, \(T\) 的前 \(j\) 个字符同样全部出现在LCS中(情况一);

对于第二个转移方程,分两种情况:

情况a: \(S\) 的前 \(i\) 个字符全部出现在LCS中, \(T\) 的前 \(j-1\) 个字符全部出现在LCS中(情况二);

情况b: \(S\) 的前 \(i-1\) 个字符全部出现在LCS中, \(T\) 的前 \(j\) 个字符全部出现在LCS中(情况三);

但是还有特殊情况,即 \(S\) 的前 \(i-1\) 个字符全部出现在LCS中, \(T\) 的前 \(j-1\) 个字符同样全部出现在LCS中(情况四)。

\(g[i][j]\) 为求方案的数组。

\[g[i][j]+=\begin{cases} g[i-1][j-1],&情况一\\ g[i][j-1],&情况二\\ g[i-1][j],&情况三\\ -g[i-1][j-1],&情况四 \end{cases} \]

情况四是因为当在计算 \(f[i][j]\) 时,已经被 \(f[i][j-1]\) (按照情况二)和 \(f[i-1][j]\) (按照情况三)计算两遍了,所以减去。

至于其他情况为什么是加号而不是等号(我脑子抽抽,第一次写成等号,于是我挂了,shift!),那是因为这个位置会经过四重情况层层检验计算(大雾)。

代码如下:

100pts:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const int N=5e3+10;
const int mod=1e8;
int n,m,a[N],b[N],f[3][N],g[3][N];

int main(){
	string s;cin>>s;
	n=s.length()-1;
	for(int i=1;i<=n;i++)a[i]=s[i-1]-'A'+1,g[0][i]=1;
	cin>>s;
	m=s.length()-1;
	for(int i=1;i<=m;i++)b[i]=s[i-1]-'A'+1,g[0][i]=1;
	g[1][0]=g[0][0]=1;
	int k=1;
	for(int i=1;i<=n;i++,k^=1){
		for(int j=1;j<=m;j++){
			g[k][j]=0;
			if(a[i]==b[j])f[k][j]=f[k^1][j-1]+1;
			else f[k][j]=max(f[k^1][j],f[k][j-1]);
			if(a[i]==b[j])g[k][j]+=g[k^1][j-1];
			if(f[k][j]==f[k][j-1])g[k][j]+=g[k][j-1];
			if(f[k][j]==f[k^1][j])g[k][j]+=g[k^1][j];
			if(f[k][j]==f[k^1][j-1])g[k][j]-=g[k^1][j-1];
			g[k][j]=(g[k][j]%mod+mod)%mod;
		}
	}
	cout<<f[k^1][m]<<endl<<g[k^1][m];
	/*cout<<endl;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)cout<<g[i][j]<<" ";
		cout<<endl;
	}*/
	return 0;
}

0pts:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;


const int N=5e3+10;
int n,top,a[N],t[N],cnt[N];
int cap[30][N];

inline int lowbit(int x){
	return x&-x;
}
inline void add(int x,int k){
	for(int i=x;i<=n;i+=lowbit(i))t[i]=max(t[i],k);
}
inline int query(int x){
	int fin=0;
	for(int i=x;i>0;i-=lowbit(i))fin=max(fin,t[i]);
	return fin;
}
inline void find(){
	for(int i=1;i<=10;i++)cout<<query(i)<<" ";cout<<endl;
}

int main(){
	string s;
	cin>>s;
	for(int i=1;i<s.length();i++){
		int x=s[i-1]-'A'+1;
		++cap[x][0];
		cap[x][cap[x][0]]=++top;
	}
	for(int i=1;i<=26;i++)cap[i][0]=0;
	cin>>s;
	n=s.length()-1;
	int maxn=0,num=0;
	for(int i=1;i<s.length();i++){
		int x=s[i-1]-'A'+1;
		++cap[x][0];
		if(!cap[x][cap[x][0]])cap[x][cap[x][0]]=++top;
		a[i]=cap[x][cap[x][0]];
		int len=query(a[i]-1)+1;
		if(len==maxn)++num;
		else if(len>maxn)maxn=len,num=1;
		add(a[i],len);
		//cout<<i<<" "<<a[i]<<" "<<len<<" "<<query(a[i]-1)<<endl;
		//find();//
	}
	//for(int i=1;i<s.length();i++)cout<<a[i]<<" ";cout<<endl;
	cout<<maxn<<endl<<num;
	return 0;
}
上一篇:如何手动获取maven项目中resource目录下的文件(包括二级目录下的文件)


下一篇:File中isFile与exists与isDirectory与getPath与getAbsolutePath与getCanonicalPath区别