11. Cacey and Calphabet

kingno

可以把字母看成26进制数,求一个最长递增子序列

Kinoko

参考 leetcode 300. 最长上升子序列
时间复杂度 $O(n^2)$,空间复杂度 $O(n)$

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

#define MAXN 51

int main()
{
    char s[MAXN]; int dp[MAXN];
    for (int i = 0; i < MAXN; i++) dp[i] = 1;
    scanf("%s", s);
    int len = strlen(s), lis_len = 1, res;
    for (int i = 1; i < len; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] = s[i] > s[j] ? max(dp[j] + 1, dp[i]) : dp[i];
            lis_len = max(lis_len, dp[i]);
        }
    }
    res = 26 - lis_len;
    printf("%d", res);
    return 0;
}
Kevin_K

Hints:变换种类数被削弱了?!!
Ps:祝在座各位普通高等学校招生全国统一考试愉忄

╮ 潜心 ╰

这个题我是交了一个最长上升子序列就过了
但是感觉好像不太严谨?.

你当前正在回复 博客/题目
存在问题!