NOJ1031 建筑群最长坡值

这次接触到了从未接触过的算法。拜其所赐,学习了一些有关动态规划的知识。这些将在其他文章里写。本题用到的就是线性动态规划(简称dp)

参考用:https://blog.csdn.net/weixin_42430270/article/details/80727227

#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int n, ans = -1;
    cin >> n;
    int* h = new int[n];
    int* dp = new int[n];
    for (int i = 0; i < n; i++)
    {
        cin >> h[i];
        dp[i] = 1;
    }
    for (int i = 0; i < n; i++)
        for (int k = 0; k < i; k++)
            if (h[k] > h[i])
                dp[i] = dp[k] + 1 > dp[i] ? dp[k] + 1 : dp[i];      //状态转移方程
    for (int i = 0; i < n; i++)
        ans = max(ans, dp[i]);
    delete[] h;
    delete[] dp;
    cout << ans;
    return 0;
}


发表评论

电子邮件地址不会被公开。