拼多多笔试第4题

拼多多第4题， 考虑一个多步决策，每次剔除的是最长升序序列或者最长降序序列，利用回溯法（递归）求解。

测试了几个案例，都过了。大家指点指点

#include<iostream>
#include<vector>
using namespace std;

bool compare(int a, int b, int order=0) {
    return order==0?a<b:a>b;// 0 ascending, 1 descending
}
vector<int> LIS(vector<int> sequence, int order=0) {
    // dp
    vector<int> dp(sequence.size(), 1);
    vector<vector<int>> pos;
    // initialize
    for(int i=0; i<sequence.size(); i++) {
        vector<int> tmp;
        tmp.push_back(i);
        pos.push_back(tmp);
    }
    for(int i=1; i<sequence.size(); i++) {
        int idx=0;
        for(int j=0; j<i; j++) {
            if(compare(sequence[j], sequence[i], order)) {
                if(dp[j]+1>dp[i]) {
                    dp[i] = dp[j]+1;
                    idx = j;
                }
            }
        }
        for(auto it: pos[idx]) {
            pos[i].push_back(it);
        }
    }
    int id=0;// find max sequence ending
    int maxL=0;
    for(int i=0;i<sequence.size(); i++) {
        if(dp[i]>maxL) {
            maxL = dp[i];
            id = i;
        }
    }

   // cout<<id<<endl;
    // delete from list
    int k = sequence.size()-maxL;
   // cout<<"k: "<<k<<endl;

    vector<int> res(k);
    int j= 0;
    for(int i=sequence.size()-1; i>=0; --i) {
        if(i==pos[id][j]) ++j;
        else {
            res[k-1] = sequence[i];
            --k;
        }
    }
    return res;
}

void printVec(vector<int>& res) {
    for(auto it: res) {
        cout<<it<<" ";
    }
    cout<<endl;
}
int leastRound(vector<int> cards) {
    if(cards.size()==0) return 0; // recursive end
    /*
    vector<int> res = LIS(cards, 0);
    printVec(res);
    res = LIS(cards, 1);
    printVec(res);
    return 0;
    */
    return min(leastRound(LIS(cards, 0))+1,
               leastRound(LIS(cards, 1))+1);
}
int main() {
    vector<int> cards;
    int n, num;
    cin>>n;
    while(n) {
        cin>>num;
        cards.push_back(num);
        --n;
    }
    cout<<leastRound(cards)<<endl;
}
}