louisfghbvc的部落格

題目連結:   https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?id=21721

題目大意:  找出最大單調遞減子序列(LDS)

思路:  同LIS演算法，只是要紀錄路徑，dp[i]+1 >= dp[j]，dp[j]可以由dp[i]再加1而來。當有這種情況時，更新path。

表示從i而來，然而同樣的path最大剛好就是越後面出現的數字，必定越長，且一樣長，長度一樣發生時，必定比之前的path大。

代碼:  

#include <bits/stdc++.h>
#define N 55
using namespace std;  

int dp[N], path[N];
void trace(string &s, int i){
    if(path[i] == -1) return;
    trace(s, path[i]);
    cout << s[path[i]];
}

int main()  
{  
    string s;
    while(cin >> s){
        int n = s.size();
        for(int i = 0; i < n; ++i) dp[i] = 1, path[i] = -1;
        for(int i = 0; i < n; ++i){
            for(int j = i+1; j < n; ++j){
                if(s[j] <= s[i] && dp[i]+1 >= dp[j]){
                    dp[j] = dp[i]+1;
                    path[j] = i;
                }
            }    
        }
        int mxi = n, mx = 0;
        for(int i = 0; i < n; ++i){
            if(mx <= dp[i]){
                mx = dp[i];
                mxi = i;
            }  
        }
        trace(s, mxi);
        cout << s[mxi];
        cout << endl;
    }
    return 0;  
}