啊！折磨我啊！要寄了！
2025-11-15 11:58:00
发布于：浙江
13阅读
0回复
0点赞
今天学习第六单元第08课-动态规划的综合应用要寄了啊！
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const int mod =1e9+7;
vector<string>num;
int n;
vector<int>dp(N);vector<int>pre(N);
bool check(int i,int j){
if(dp[i]!=dp[j]) return dp[i]<dp[j];
string t1="";
string t2="";
while(i){
t1=num[j]+t1;
i=pre[i];
}
while(j){
t2=num[j]+t2;
j=pre[j];
}
return t1>t2;
}
int main(){
string s;cin>>s;
string tmp="";
for(int i=0;i<s.size();i++){
if(s[i]>='A'&&s[i]<='Z'){
num.push_back(tmp);
tmp="";
}
tmp+=s[i];
}
num.push_back(tmp);
n=num.size();
int ans=0;
for(int i=1;i<n;i++){
dp[i]=1;
for(int j=1;j<i;j++){
if(num[i]>num[j]){
if(dp[i]<dp[j]+1){
pre[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=i;
}
string res="";
while(ans){
res=num[ans]+res;
ans=pre[ans];
}
cout<<res<<"\n";
return 0;
}
为我准备后事吧！
有帮助，赞一个