【过题记录】7.20

算法：动态规划

其实这就是一个线段覆盖问题，只不过大线段能够包含小线段。
这就启发我们，对于每个大线段分别跑一个dp，合并在他内部的小线段。而后对于每一个大线段，再跑一个总的dp即可。

也可以只跑一遍dp，有一个小trick，在线段两端添0，这样答案就等同于f[0]

#include<bits/stdc++.h>
using namespace std;#define int long longconst int N = 6e3+100;
int n;
int f[N];
int l[N],r[N];
int a[N];struct Node{int l,r,x;
}b[N];int g[N];
int dp[N];bool cmp(Node x,Node y){int l1 = x.r-x.l+1;int l2 = y.r-y.l+1;return l1 < l2;
}signed main(){cin>>n;for (int i = 1; i <= 2*n; i++){cin>>a[i];if (l[a[i]] == 0) l[a[i]] = i;else r[a[i]] = i;}for (int i = 1; i <= n; i++)b[i] = {l[i],r[i],i};sort(b+1,b+n+1,cmp);for (int i = 1; i <= n; i++){int x = b[i].x;for (int j = 1; j <= 2*n; j++) g[j] = 0;for (int j = b[i].l; j <= b[i].r; j++){g[j] = g[j-1]+x;if (l[a[j]] < j && l[a[j]] > b[i].l)g[j] = max(g[l[a[j]]-1]+f[a[j]],g[j]);}f[x] = g[b[i].r];}for (int i = 1; i <= 2*n; i++){dp[i] = max(dp[i-1],dp[i]);if (l[a[i]] == i) continue;dp[i] = max(dp[i],dp[l[a[i]]-1]+f[a[i]]);}cout<<dp[2*n];return 0;
}

#include<bits/stdc++.h>
using namespace std;#define int long longconst int N = 6e3+100;
int n;
int f[N];
int l[N],r[N];
int a[N];struct Node{int l,r,x;
}b[N];int g[N];
int dp[N];bool cmp(Node x,Node y){int l1 = x.r-x.l+1;int l2 = y.r-y.l+1;return l1 < l2;
}signed main(){cin>>n;for (int i = 2; i <= 2*n+1; i++){cin>>a[i];if (l[a[i]] == 0) l[a[i]] = i;else r[a[i]] = i;}for (int i = 1; i <= n; i++)b[i] = {l[i],r[i],i};b[n+1] = {1,2*n+2,0}; ++n;sort(b+1,b+n+1,cmp);for (int i = 1; i <= n; i++){int x = b[i].x;for (int j = 0; j <= 2*n; j++) g[j] = 0;for (int j = b[i].l; j <= b[i].r; j++){g[j] = g[j-1]+x;if (l[a[j]] < j && l[a[j]] > b[i].l)g[j] = max(g[l[a[j]]-1]+f[a[j]],g[j]);}f[x] = g[b[i].r];}cout<<f[0];
//	for (int i = 1; i <= 2*n; i++){
//		dp[i] = max(dp[i-1],dp[i]);
//		if (l[a[i]] == i) continue;
//		dp[i] = max(dp[i],dp[l[a[i]]-1]+f[a[i]]);
//	}
//	cout<<dp[2*n];
//	for (int i = 1; i <= n; i++) cout<<"i = "<<f[i]<<endl;return 0;
}

算法：KMPdp

这题只是一个加强版的LCS，只不过多了一个子串的限定。
所以我们不难想到状态设置:
$f[i][j][k]$表示第一个串从1……i，第二个串从2……j，匹配了第三个串k个长度的最长LCS
关键就是第三维状态的转移，我们不能随便转移，而是利用KMP的NEXT数组进行转移
在第三个串的k位之后加入s[i]，利用NEXT数组转移到相应的位置进行转移。
由于本题要求输出路径，有两种方法
第一种就是常规的求最长长度，而后利用状态关系倒序递归输出。
第二种就是直接用string去存储答案。
这里用的第二种方法

#include<bits/stdc++.h>
using namespace std;const int N = 1e2+10;
string f[N][N][N];
int n,m,q;
char s1[N],s2[N],s3[N];
int Ne[N];void KMP(){Ne[1] = 0;int j = 0;for (int i = 2; i <= q; i++){while (j > 0 && s3[i]!=s3[j+1]) j=Ne[j];if (s3[i] == s3[j+1]) j++;Ne[i] = j;}
}void Com(string &a,string b){if (a.size() < b.size()) a = b;
}int main(){cin>>(s1+1); cin>>(s2+1); cin>>(s3+1);n = strlen(s1+1); m = strlen(s2+1); q = strlen(s3+1);KMP();for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){for (int k = 0; k < q; k++){Com(f[i][j][k],f[i-1][j][k]);Com(f[i][j][k],f[i][j-1][k]);if (s1[i]!=s2[j]) continue;int now = k;while (now && s1[i]!=s3[now+1]) now = Ne[now];if (s1[i] == s3[now+1]) now++;Com(f[i][j][now],f[i-1][j-1][k]+s1[i]);}}}string ans = "";for (int i = 0; i < q; i++)Com(ans,f[n][m][i]);if (ans.size() == 0) cout<<0; else cout<<ans;return 0;
}

算是一个比较典的KMPdp的题目