动态规划(C++)

这道题学到了一个很吊的知识：

Dilworth定理:
最少的下降序列个数就等于整个序列最长上升子序列的长度

下面这个是知识博客链接

https://blog.csdn.net/litble/article/details/85305561?ops_request_misc=&request_id=&biz_id=102&utm_term=dilworth%E5%AE%9A%E7%90%86&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-6-85305561.first_rank_v2_pc_rank_v29&spm=1018.2226.3001.4187

#include<iostream>
#define INT_MIN     (-2147483647 - 1)
#define INT_MAX       2147483647
using namespace std;

int cost(int* hight,int num){
    int temp;
    int last_min = hight[0];
    int max_num = INT_MIN;
    int* long_list = new int[num];
    for (int i = 0; i < num; i++) long_list[i] = 1;
    for (int i = 1; i < num; i++) {
        temp = 0;
        for (int j = 0; j < i; j++) {
            if (hight[j] >= hight[i])
            {
                temp = max(long_list[j],temp);
            }
        }
        long_list[i] = temp + long_list[i];
        max_num = max (max_num,long_list[i]);
        
    }
    
    return max_num;
}

//Dilworth定理 最少的下降序列个数就等于整个序列最长上升子序列的长度
int times(int* lists, int num){
    int temp;
    int last_min = lists[0];
    int max_num = INT_MIN;
    int* long_list = new int[num];
    for (int i = 0; i < num; i++) long_list[i] = 1;
    for (int i = 1; i < num; i++) {
        temp = 0;
        for (int j = 0; j < i; j++) {
            if (lists[j] < lists[i])
            {
                temp = max(long_list[j],temp);
            }
        }
        long_list[i] = temp + long_list[i];
        max_num = max (max_num,long_list[i]);
        
    }
    return max_num;
}

int main(){
    int num;
    int* hight;
    cin >> num;
    hight = new int[num];
    
    for( int i = 0;i < num; i++){
        cin >> hight[i];
    }
    
    cout << cost(hight,num) << endl;
    cout << times(hight,num) <<endl;
}