游园安排

题目 游园安排

思路分析

第一次感受到如此无助 发现自己写代码的能力确实不够

思路很容易想 实现的时候卡老半天……

甚至一开始的提取单词都卡了一下 到后面的回溯最长上升子序列又卡住了 只会算长度不知道怎么回溯路径 唉

为什么最后只有3/10 好像是因为有个字典序顺序 这个方法会打乱顺序 然后最后几个案例还有mle tle等等……啧 难搞

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

vector<string> words;

vector<vector<int>> lcs_length(const vector<string>& X, const vector<string>& Y) {
    int m=X.size();
    int n=Y.size();
    vector<vector<int>> dp(m+1,vector<int>(n+1, 0));

    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++) {
            if(X[i-1]==Y[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    return dp;
}

vector<string> build_lcs(const vector<vector<int>>& dp, const vector<string>& X, const vector<string>& Y) {
    int i = X.size(), j = Y.size();
    vector<string> lcs;
    while(i > 0 && j > 0) {
        if(X[i-1]==Y[j-1]) {
            lcs.push_back(X[i-1]);
            i--;
            j--;
        }
		else if(dp[i-1][j]>dp[i][j-1])
            i--;
        else
            j--;
    }
    reverse(lcs.begin(), lcs.end());
    return lcs;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    string orig;
    cin >> orig;
    string tmp;
    for(int i = 0; i < orig.size(); i++) {
        if(isupper(orig[i])){
            if(!tmp.empty()) {
                words.push_back(tmp);
            }
            tmp = orig[i];
        }
        else
            tmp += orig[i];
    }
    if(!tmp.empty())
        words.push_back(tmp);

    vector<string> copy = words;
    sort(words.begin(), words.end());

    auto dp = lcs_length(copy, words);
    vector<string> lcs = build_lcs(dp, copy, words);

    for(auto word:lcs)
        cout<<word;

    return 0;
}

同类题型

视频讲解

⬅️ 皮亚诺曲线距离 🏠 00-冲刺国赛 ➡️ 答疑