题目传送门：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=18201

其实是一道不算难的DP，但是搞了好久，才发现原来是题目没读清楚，囧，原序列那里简直太坑了，

看了别人好多的都是用最长公共子序列，但是我用的是最长上升子序列来做，就是将原序列逐渐递增映射成递增的数列，这道题目的数据恰好符合这个条件

比如正确的序列为$$5 \ 6 \ 4  \ 1 \  3 \  2$$,我就可以将他一一映射成为

$$ID[5]\rightarrow 1$$      $$ID[6]\rightarrow 2$$      $$ID[4]\rightarrow 3$$

$$ID[1]\rightarrow 4$$   $$ID[3]\rightarrow 5$$ $$ID[2]\rightarrow 6$$

面对于另一个序列的时候如：$$ 6 \ 1\  3 \ 2 \ 5\  4$$

那么我就可以将他映射成为   $$ 2 \ 4 \ 5 \ 6 \ 1 \ 3$$  转换成求该序列的最长上升子序列了哈。

直接贴代码：

#include <cstdio>#include <cstring>#include <iostream>using namespace std;const int maxn = 30;int ID[maxn];int b[maxn];int ans1,ans2;int a[maxn];int c[maxn];int n;int opt[maxn];int solve(){    int MAX = 0;    a[0] = -100;    memset(opt,0,sizeof(opt));    for(int i = 1;i <= n;++i)    for(int j = 0;j <= i-1;++j){        if(a[j] <= a[i])            opt[i] = max(opt[i],opt[j] + 1);    }    for(int i = 1;i <= n;++i){        MAX = max(MAX,opt[i]);    }    return MAX;}void print(){    for(int i = 1;i <= n;++i)        cout<<a[i]<<" ";    cout<<endl;}int getid(int index){    for(int i = 1;i <= n;++i)        if(ID[i] == index)        return i;}int main(){    //freopen("in.txt","r",stdin);    int fuck;    while(~scanf("%d",&n)){        for(int i = 1;i <= n;++i){            scanf("%d",&fuck);            ID[fuck] = i;        }        while(1){            ans1 = 0;            for(int i = 1;i <= n;++i){                if(scanf("%d",&fuck)==EOF) goto holly_shit;                a[fuck] = getid(i);            }            printf("%d\n",solve());            memset(a,0,sizeof(a));        }        holly_shit: continue;    }    return 0;}

UVA 111 简单DP 但是有坑