//【模板】最长公共子序列
	//一、LCS 时间n*n空间n*n解法
	for i:0->n
		for j:0->n
			if ai==bj
				f[i][j]=f[i-1][j-1]+1//自己解决溢出，比如f[i+1][j+1]=f[i+1][j+1]+1
			else
				f[i][j]=max(f[i-1][j],f[i][j-1])


	//二、LCS 时间n*n 空间n解法
	// 我们发现只用了f[i][j]、f[i-1][j-1]、f[i-1][j-1]、f[i][j-1]，所以原来n行n列只用了最后两行，那果断滚动数组
	for i:0->n
		for j:0->n
			turn^=1
			if ai==bj
				f[turn][j]=f[turn^1][j-1]+1//自己解决溢出，比如f[i+1][j+1]=f[i+1][j+1]+1
			else
				f[turn][j]=max(f[turn^1][j],f[turn][j-1])

	//三、特殊LCS转LIS(如果有重复元素，时间复杂度降为nmlognm比上面那个还差) 时间nlogn 空间n解法
	/*测试用例很友好，第二行b串是上升，根据这个想到第一行a串上升子序列就是公共子序列。
	//但是真正的全排列中b串未必是上升的，坐标必然是上升的，所以考虑存元素到坐标的映射关系
5 
3 2 1 4 5
1 2 3 4 5
	*/
	for j:0->n	
		ind[b[j]]=j//ind记录b[j]元素到索引j的映射
	for i:0->n
		a[i]=ind[a[i]]//a[i]元素通过上述映射关系映射成a[i]元素在b串中的坐标，即将a[i]元素序列还原成在b串中的相对位置序列，对这个序列求LIS即LCS
	对a序列求LIS

3 comments

  • @ 2025-4-2 0:42:21 
    #include<iostream>
#include<cstring>
#include<climits>
using namespace std;
const int maxn=1E3+10, inf=INT_MAX;
int n,c[maxn],t,dp[maxn][maxn];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>c[i];
	for(int l=n;l>=1;l--){
		dp[l][l]=1;
		dp[l][l+1]=1 + (c[l]!=c[l+1]);//这里不特判的话 dp[l][l+1]在c[l]==c[r]时dp[l][l+1]=dp[l+1][l]=0 
		for(int r=l+2;r<=n;r++){
			if(c[l]==c[r])	dp[l][r]=dp[l+1][r-1];
			else{//大错特错胡写写成else	dp[l][r]=min(dp[l+1][r], dp[l][r-1])+1;想当然以为像	[IOI 2000] 回文字串。但这题区间转移不是左右端扩展的。和合并石子相似，需要枚举分割区间 
				dp[l][r]=inf;
				for(int k=l;k<r;k++)
					dp[l][r]=min(dp[l][r], dp[l][k]+dp[k+1][r]);
			}
		}
	}
	cout<<dp[1][n];
	return 0;
}
  • @ 2025-3-30 21:34:32

    [NOIP2015 提高组] 子串

    //
////题目都有取模运算了，不动脑子都知道答案数很大，硬枚举所有搜索路径计数肯定不可行
////没思路还是先写搜索的搜法（加记忆化剪枝就变DP了），很容易想到dfs(i,j,cnt)表示到a串的第i个位置为止使用cnt个子串匹配b串前j位字符。
////由于是子串，所以每个cnt子串，i得连续，所以得再加一个状态记第i个字符选或者不选，目标串的每个元素b[j]都是肯定要选的
//#include<iostream>
//#include<cstring>
//using namespace std;
//const int maxn=1E3+10, maxm=2E2+10, mod=1000000007;//注意如果开int三次mod相加就够溢出了
//int n,m,k;
//char a[maxn],b[maxn];
//int f[maxn][maxm][maxm][2];
//int main(){
//	cin>>n>>m>>k;
//	cin>>a+1>>b+1;
//	// cout<<a+1<<" "<<b+1<<endl;
//	f[0][0][0][0]=1;//=f[0][0][0][1]=0;//注意初始化，串起始点是一种方案
//	for(int i=1;i<=n;i++){
//		f[i-1][0][0][0]=1;//=f[i-1][0][0][1]=0;//注意初始化，串起始点是一种方案
//		for(int j=1;j<=m;j++){
//			for(int c=1;c<=k;c++){
//				if(a[i]==b[j]){
//					f[i][j][c][1]=(f[i-1][j-1][c][1]/*a[i-1]和a[i]连着选*/ + (f[i-1][j-1][c-1][0]+f[i-1][j-1][c-1][1])%mod/*断开新一子串*/)%mod;
//				}else{
//					f[i][j][c][1]=0;//a[i]!=b[j]那还非得选这个字符，根本没这个方案
//				}
//				f[i][j][c][0]=(f[i-1][j][c][0]+f[i-1][j][c][1])%mod;
//			}
//		}
//	}
//	cout<<(f[n][m][k][1]+f[n][m][k][0])%mod;
//	return 0;
//}

//MLE了！果断滚动数组
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=1E3+10, maxm=2E2+10, mod=1000000007;//注意如果开int三次mod相加就够溢出了
int n,m,k;
char a[maxn],b[maxn];
int f[2][maxm][maxm][2],turn=0;
int main(){
	cin>>n>>m>>k;
	cin>>a+1>>b+1;
	for(int i=1;i<=n;i++){
		f[turn][0][0][0]=1;//=f[i-1][0][0][1]=0;//注意初始化，串起始点是一种方案
		turn^=1;
		for(int j=1;j<=m;j++){
			for(int c=1;c<=k;c++){
				if(a[i]==b[j]){
					f[turn][j][c][1]=(f[turn^1][j-1][c][1]/*a[i-1]和a[i]连着选*/ + (f[turn^1][j-1][c-1][0]+f[turn^1][j-1][c-1][1])%mod/*断开新一子串*/)%mod;
				}else{
					f[turn][j][c][1]=0;//a[i]!=b[j]那还非得选这个字符，根本没这个方案
				}
				f[turn][j][c][0]=(f[turn^1][j][c][0]+f[turn^1][j][c][1])%mod;
			}
		}
	}
	cout<<(f[turn][m][k][1]+f[turn][m][k][0])%mod;
	return 0;
}
    • @ 2025-3-30 21:04:45
      Edited

      [IOI2000] 回文字串

      //搜索记忆化，借助递归实现自底向上从中间向两边扩展回文串的处理
// #include<bits/stdc++.h>
// using namespace std;
// string x;//Ab3bd
// int dp[1005][1005];
// int p(int l,int r){
// 	if(dp[l][r])return dp[l][r];
// 	if(l>=r)return 0;
// 	if(x[l]==x[r])return p(l+1,r-1);
// 	else return dp[l][r]=min(p(l+1,r),p(l,r-1))+1;
// }
// int main(){
// 	cin>>x;
// 	cout<<p(0,x.size()-1);
// 	return 0;
// }

      // //方法1：暴力很容易想到回文串是中间向两端扩展的。进化一下就是区间DP记录左右端点状态
// //ab->aba,1  Ab3bdA->Adb3bdA,1
// #include<iostream>
// #include<cstring>
// using namespace std;
// const int maxl=1E3+10;
// char s[maxl];
// int dp[maxl][maxl];//dp[i][j]表示s[i~j]改造成回文串需要插入的最少字符数
// int main(){
// 	cin>>s;//如果想字符串坐标右移一位可以直接cin>>s+1;
// 	for(size_t l=0;l<strlen(s);l++){
// 		dp[l][l]=0;//初始化，和下面的逻辑配合
// 	}
// 	for(int len=1;len<maxl;len++){//枚举长度，这个放内外循环都是长度长的回文串建立在短的基础上，这样正好规避长度奇偶性等的问题
// 		for(size_t l=0,r=l+len;r<strlen(s);l++,r++){//枚举左端点
// 			if(s[l]==s[r]){
// 				dp[l][r]=dp[l+1][r-1];					//min(dp[l+1][r-1],  min(dp[l+1][r],dp[l][r-1])+1);
// 			}else{
// 				dp[l][r]=min(dp[l+1][r],dp[l][r-1])+1;	//min(dp[l+1][r-1]+2,min(dp[l+1][r],dp[l][r-1])+1);
// 			}
			
// 		}
// 	}
// 	cout<<dp[0][strlen(s)-1];
// 	return 0;
// }

/*
  	0a	1b	2c
0c	0	0	1
1b	0	1	1
2a	1	1	1
*/
/*
  	0a	1b	2c	3a
0a	0	1	2	2
1b		0	2	2
2c			0	1
3a				0
*/
// //方法1空间优化，发现只会用到dp[l+1][r-1]，dp[l+1][r],dp[l][r-1]，那肯定可以改滚动数组/降一维
// //由于想利用[l]和[l+1]滚动数组，那外围循环就得固定l
// #include<iostream>
// #include<cstring>
// using namespace std;
// const int maxl=1E3+10;
// char s[maxl];
// int dp[2][maxl],turn=0;//dp[j]表示s[0~j]改造成回文串需要插入的最少字符数
// int main(){
// 	cin>>s;//如果想字符串坐标右移一位可以直接cin>>s+1;
// 	for(size_t l=0;l<strlen(s);l++){
// 		dp[0][l]=dp[1][l]=0;//初始化，和下面的逻辑配合
// 	}
// 	// for(int l=0;l<strlen(s)-1;l++){//用abc、abca测就知道不能这么写。l正向枚举dp[turn^1][r]可能用的是上上轮的，上轮没有覆盖掉这部分
// 	for(int l=strlen(s)-2;l>=0;l--){//而且l反向r正向枚举正好控制长度从小往大扩展
// 		turn^=1;
// 		for(int r=l+1;r<strlen(s);r++){
// 			if(s[l]==s[r]){
// 				dp[turn][r]=dp[turn^1][r-1];					//dp[l][r]=dp[l+1][r-1];				
// 			}else{
// 				dp[turn][r]=min(dp[turn^1][r],dp[turn][r-1])+1;	//dp[l][r]=min(dp[l+1][r],dp[l][r-1])+1;
// 			}
// 			// cout<<dp[turn][r]<<" ";
// 		}
// 		// cout<<endl;
// 	}
// 	cout<<dp[turn][strlen(s)-1];
// 	return 0;
// }

// //方法2：转化成最长公共子序列：正序与倒序“公共”的部分就是我们回文的部分，剩余的字符就是要添加的字符
//  #include<iostream>
//  #include<cstring>
//  using namespace std;
//  const int maxl=1E3+10;
//  char s[maxl];
//  int dp[maxl][maxl];//dp[i][j]表示s[0->i]和s[j<-len]的最长公共子序列
//  int main(){
//  	cin>>s;
//  	for(int l=0;l<strlen(s);l++){//枚举正向扫终点
//  		for(int r=strlen(s)-1;r>=0;r--){//反向
//  			if(s[l]==s[r]){
//  				dp[l][r]=dp[l-1][r+1]+1;					
//  			}else{
//  				dp[l][r]=max(dp[l-1][r],dp[l][r+1]);	
//  			}	
//  		}
//  	}
//  	cout<<strlen(s)-dp[strlen(s)-1][0];
//  	return 0;
//  }

//方法2空间改滚动数组，时间n^2，空间n
#include<iostream>
 #include<cstring>
 using namespace std;
 const int maxl=1E3+10;
 char s[maxl];
 int dp[2][maxl],turn=0;
 int main(){
 	cin>>s;
 	for(int l=0;l<strlen(s);l++){//枚举正向扫终点
		turn^=1;
 		for(int r=strlen(s)-1;r>=0;r--){//反向，或者把数组逆序复制再正向扫好理解一点
 			if(s[l]==s[r]){
 				dp[turn][r]=dp[turn^1][r+1]+1;					
 			}else{
 				dp[turn][r]=max(dp[turn^1][r],dp[turn][r+1]);	
 			}	
 		}
 	}
 	cout<<strlen(s)-dp[turn][0];
 	return 0;
 }
      ❤️ 1
      • 1
      101
      Accepted
      0
      Solutions Liked
      1. About
      2. Contact Us
      3. Privacy
      4. Terms of Service
      5. Copyright Complaint
      6. Language
      7. Legacy mode
      8. Theme
      2. 粤ICP备2022044963号-1
      3. Worker 0, 20ms
      4. Powered by Hydro v4.13.3 Community