首页 > 代码库 > 动态规划：最长上升子序列

动态规划：最长上升子序列

2024-10-29 19:49:39   204人阅读

Description

        A string of lowercase letters is calledalphabeticalif deleting zero or more of its letters can result inthealphabet string"abcdefghijklmnopqrstuvwxyz".

Given a strings, determine the minimum number of letters to insert anywhere in the string tomake it alphabetical.

Input

       The input consists of one or more test cases，Each test case consists of one line containing of a strings(1<= |s| <=50).

It is guaranteed thatsconsists of lowercase ASCII letters `a‘ to `z‘ only.

Output

        Print, on a single line, a single integer indicating the minimum number of letters that must beinserted in order to make the stringsalphabetical

Sample

//Sample Input
xyzabcdefghijklmnopqrstuvw
aiemckgobjfndlhp


//Sample Output
3
20

题意：

        给定一个字符串，通过删除一些元素，再添加一些元素，使之成为字母表，即"abcdefghijklmnopqrstuvwxyz"，问最少需要添加多少元素

思路：

       求最长上升子序列，用26减去最长的上升子序列的值即结果。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
#include<stdio.h>
int main()
{
    char c[1000];
    int n,i,j,num,maxx[1000];
    while(~scanf("%s",c))
    {
        num=1;
        for(i=0; i<1000; ++i)
        {
            maxx[i]=1;//数组存以第i个数为终点的最长上升序列  并且初始化为1
        }
        for(i=1; c[i]!=0; ++i)
            for(j=0; j<i; ++j)
            {
                if(c[j]<c[i]&&maxx[j]+1>maxx[i])////在前i-1个序列中，寻找以终点小于c[i]的最长的子序列，即最优子状态  
                    maxx[i]=maxx[j]+1;
                if(num<maxx[i])
                    num=maxx[i];//num用来记录最优序列长度 
            }
        printf("%d\n",26-num);
    }
    return 0;
}

 

动态规划：最长上升子序列


联系
我们