PAT A1045 动态规划

栏目: 编程工具 · 发布时间: 6年前

内容简介:该题目有两种解法,都是动态规划中特别经典的解法,一种是最长不下降子序列,一种是最长公共子序列;第一种方法对于该题目其实有点取巧的感觉;

PAT A1045 动态规划

该题目有两种解法,都是动态规划中特别经典的解法,一种是最长不下降子序列,一种是最长公共子序列;

第一种方法对于该题目其实有点取巧的感觉;

首先,注意一点,对于最长不下降子序列来说,其序列的元素一定是非递减的,所以我们的当务之急是如何将值转换为

递增序列,从而使得算法能够继续进行;

对于这个问题,我们可以使用hashtable进行处理,也就是利用hashtable重新使得值递增;

这里需要注意一下,子序列递增研究的是不连续的子序列,连续的子序列其实可以用前面的KMP算法来及进行解决;

对于该问题,首当其中的还是状态转移方程。由于该问题还是从0开始研究,所以仍然设置一个一维数组dp来储存中间的状态;

大致思路是限定一个子串序列,然后选择一个,从第一个开始进行轮询,这里有点像插入 排序 的感觉;

其状态转移方程为dp[i]=max(1,dp[j]+1);

该方程可以理解将第i个元素排在j后面,从而继承j之前的子串序列的长度,1为单个元素的序列长度;

代码如下:

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
const int maxc=210;
const int maxn=10010;
int Hashtable[maxc];
int a[maxn],dp[maxn];
int main(){
    int n,m,x;
    scanf("%d%d",&n,&m);
    memset(Hashtable,-1,sizeof(Hashtable));
    for(int i=0;i<m;i++){
        scanf("%d",&x);
        Hashtablet[x]=i;
    }
    int L,num=0;
    scanf("%d",&L);
    for(int i=0;i<L;i++){
        scanf("%d",&x);
        if(Hashtable[x]>=0){
            a[num++]=Hashtable[x];
            //进行hashtable的相应转换
        }
    }
    int ans=-1;
    for(int i=0;i<num;i++){
        dp[i]=1;
        for(int j=0;j<i;j++){
            if(a[j]<=a[i]&&dp[i]<dp[j]+1){
                dp[i]=dp[j]+1;
            }
        }
        ans=max(ans,dp[i]);
    }
    printf("%d\n",ans);
    return 0;
}

第二种不太好理解,所以这里先不再赘述,主要是不能理解为什么公共部分可以重复输出;


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

C++沉思录

C++沉思录

Andrew Koenig、Barbara Moo / 黄晓春、孟岩(审校) / 人民邮电出版社 / 2002-11-01 / 50.00元

《C++ 沉思录》集中反映了C++的关键思想和编程技术,不仅告诉你如何编程,还告诉你为什么要这样编程。本书曾出现在众多的C++专家推荐书目中。 这将是C++程序员的必读之作。因为: 它包含了丰富的C++思想和技术,从详细的代码实例总结出程序设计的原则和方法。 不仅教你如何遵循规则,还教你如何思考C++编程。 既包括面向对象编程也包括泛型编程。 探究STL这一近年来C++最重要的新成果的内在思想。一起来看看 《C++沉思录》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具