U6-07-二维动态规划
原题链接：67324.4.0U5笔记合集
2025-12-27 12:05:48
发布于：江苏
10阅读
0回复
0点赞
#include <bits/stdc++.h>
#include <vector>
using namespace std;
const int N = 1e4+5;
vector<string> num;
int dp[N], pre[N];
int main(){
string s;
cin >> s;
int len = s.size();
string tmp = "";
for (int i=0; i<len; i++){
if (s[i]>='A' && s[i]<='Z'){
num.push_back(tmp);
tmp = "";
}
tmp += s[i];
}
num.push_back(tmp);
int n = num.size();
int ans = 0;
for (int i=1; i<n; i++){
dp[i] = 1;
for (int j=1; j<i; j++){
// dp[i] = max(dp[i], dp[j] + 1);
if (num[i] > num[j]){ //上升序列
if (dp[i] < dp[j] +1){
pre[i] = j; //记录下标 //第i个人的前一个下标是j
dp[i] = dp[j] + 1;
}else if(dp[i] == dp[j] + 1){
if(num[pre[i]] > num[j]) { //字典序最小
pre[i] = j;
}
}
}
}
if (check(ans, i)) ans = j; //序列是否合理
}
//不停地找到之前的元素，拼接， 最后输出
string res = "";
while (ans){
res = num[ans] + res;
ans = pre[ans];
}
cout << res;
return 0;
}
这里空空如也
有帮助，赞一个