啊！折磨我啊！要寄了！

复仇者_天之神_ZDZL_恶魔

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;
}

为我准备后事吧！

有帮助，赞一个

去预览

0/2000

全部评论 1

TN Hacker
致敬池塘守护者

2025-12-21 来自北京
0

全部评论 1

热门讨论