线性dp求具体方案
线性dp中的 求最长上升子序列 我们很容易求出 是多长 或者 和最大为多少
但具体是选择了哪些呢 发现突然一问还是有点懵
回溯路径这里复习一下
最长上升子序列 因为选择不外乎就是前面的某个和现在进行比较
所以可以在更新的时候记录从哪里转移而来 然后使用回溯路径的方式（pre）实现路径输出
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N=1010;
int a[N];
int f[N];//考虑到第i个数 以i结尾的最长上升子序列的所有情况 属性max
int n;
int g[N];//记录路径
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=1;i<=n;i++){
f[i]=1;
g[i]=0;//0 表示只有一个数
for(int j=1;j<i;j++){
if(a[j]<a[i]) //f[i]=max(f[i],f[j]+1);
{
if(f[j]+1 > f[i]){
f[i]=f[j]+1;
g[i]=j;//记录从j转移到i
}
}
}
}
int res=0;
int k=0;//记录最大值的下标
for(int i=1;i<=n;i++){
res=max(res,f[i]);
if(f[i]>f[k])
k=i;
}
cout<<res<<endl;
//此时 k为最大值的下标 最长的长度为f[k]
//又有g[]一路记录某点是由哪个点转移而来 自然可以倒推
//当然这样得到的是逆序的 可以存在数组中 reverse一下
vector<int> ans;
for(int i=0,len=f[k];i<len;i++){
ans.push_back(a[k]);
k=g[k];
}
reverse(ans.begin(),ans.end());
for(auto x:ans) cout<<x<<" ";
return 0;
}
最长公共子序列
选择比较多 要考虑 A中第i个在不在里面 B中第j个在不在里面 不方便记录到底从哪里转移而来
这里选择和背包回溯一样的方法 倒着再做一遍 如果有相等就选择（贪心思想） 可能不是唯一解 但一定是一个解
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> n >> m;
cin >> a + 1 >> b + 1;
for (int i = 1; i <= n; i ++){
for (int j = 1; j <= m; j ++){
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
}
cout << f[n][m] << endl;
string res;
// 一个倒序的过程
for (int i = n, j = m; i && j; )
{
if (a[i] == b[j]) res += a[i], i --, j --;
else if (f[i - 1][j] > f[i][j - 1]) i --;
else j --;
}
reverse(res.begin(), res.end());
cout << res << endl;
return 0;
}
这里再挂一下游园安排的重写代码 虽然还是不能ac
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
vector<string> words;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
string og; cin>>og;
string tmp;
for(int i=0;i<og.size();i++){
if(isupper(og[i])){
if(!tmp.empty()){
words.push_back(tmp);
}
tmp=og[i];
}
else
tmp+=og[i];
}
if(!tmp.empty())
words.push_back(tmp);
vector<string> copy(words);
sort(words.begin(),words.end());
copy.insert(copy.begin()," ");
words.insert(words.begin()," ");
//lcs
int n=copy.size()-1,m=words.size()-1;
vector<vector<int>> f(n+1,vector<int>(m+1,0));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(copy[i]==words[j])
f[i][j]=f[i-1][j-1]+1;
else
f[i][j]=max({f[i-1][j-1],f[i-1][j],f[i][j-1]});
}
}
//回溯
vector<string> res;
for(int i=n,j=m;i&&j;){
if(copy[i]==words[j]){
res.push_back(copy[i]);
i--;
j--;
}
else if(f[i-1][j]>f[i][j-1])
i--;
else
j--;
}
reverse(res.begin(),res.end());
for(auto x:res){
cout<<x;
}
return 0;
}
💬 评论