编号（长度）为状态的动态规划（LCS，LIS等）

这一系列的文章是一步步的按照Amber大牛的DP总结一步步的写各个分类的DP的记录。

之后做DP会更新增加这一系列的文章的内容的。

共性总结

本类的状态是基础的基础，大部分的动态规划都要用到它，成为一个维。

一般来说，有两种编号的状态：

状态（i）表示前i个元素决策组成的一个状态。

状态（i）表示用到了第i个元素，和其他在1到i-1间的元素，决策组成有的一个状态。

题库：

a)最长的不下降子序列（LIS）（有O（n^2）,O(nlgn)两种）

以一元组(i)作为状态，表示第i个作为序列的最后一个点的时候的最长序列。于是很容易想到O(n2)得算法。但本题可合理组织状态，引入一个单调的辅助数组，利用单调性二分查找，优化到O(nlogn)。

O(n^2):

很显而易见的DP方程，

状态：dp[i]表示到第i个元素为结尾的最长不下降子序列的长度。

状态转移方程：dp[i] = max(dp[j])+ 1 (j <i&& num[i] <= num[j] );

O（n * lgn） :

状态：f[i]表示长度为i的最长不下降子序列最后一个元素的最大的值。f数组一定是单调的

状态转移方程：如果第i个元素小于等于于当前最长len的f[len],则f[++len] = num[i] ;

否则二分去找最靠后的f[]使得其值大于等于当前的值，更新其后面那个长度的f值后就可以了的。

题目：

拦截导弹(NOIP99 Advance 1)

http://acm.nuaa.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=1005

这题之前做的是http://judge.noi.cn/problem?id=1084这个题目的，因为不知道数据范围，所以用的nlgn的算法。

这题第一个问题很明显的最长不下降子序列的。第二个问题，我之前想的是一直去找最长不下降子序列，然后记录最长的那个上的元素，直到没有被标记的就结束了的。写了后交了结果是40分，把我郁闷到了。正好红薯在边上，他说这个第二问有另外一种方法，就是利用Dilworth去求解最小链划分等于最长反链。相关证明在http://hi.baidu.com/lambda2fei/blog/item/c48f61a531f20bfb9152eec0.html

其实我理解就是，在一个偏序集里面，如果一个满足偏序集的一个最小的划分，等于与此偏序集相反的比较的那个偏序集的最长链。。。就是说：最长不下降子序列的最小划分等于最长上升子序列；最长不上升子序列的最小化分等于最长下降子序列等等。。。。如果想深入研究请参考那篇blog我是没看懂证明过程。

写完之后交了还是得了40分，把我郁闷到了。然后还有一个oier找我说我过了，问我咋做的，我回复说我才得到了40分。郁闷到了，就直接在南航的那个交了，结果1Y。。。囧。。。。

Beautiful People (sgu199)

http://acm.sgu.ru/problem.php?contest=0&problem=199

这题题意就是说给你N个人，分别有两个属性，s, b.如果两个人s1< s2 &&b1<b2 || s1>s2 &&b1>b2才能在一起，现在问你能有最多有多少个人可以再一起。然后输出最多的人数，和人的标号。n的范围10^5;

直接对第一维s排序（排序当s相等的时候，把b大的放在前面）然后就是一个最长上升子序列了的。因为n比较大，所以你不能n^2的去做，只能nlgn的去做，但是这个题目要输出路径，所以要想下那个nlgn的过程，然后那个路径如何去记录的。

nlgn的过程中，是以长度为下标的。是要不断的更新的，所以你在记录path的过程中，是要有另外的一个辅助数组去记录长度为i的此时是标号为几的index数组。然后在DP的过程中去更新他们。在输出的过程中，不能一直按照path去递归的去输出，要找到最长的那个最后一个元素是谁，然后跑一个长度len的循环去输出解。。

代码：code:+ expand sourceview plaincopy to clipboardprint?#include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> using namespace std; int kx[100005]; int path[100005]; int len ; struct node{ int a,b; int index ; }stu[100005]; int flage[100005]; bool cmp(const struct node p1 , const struct node p2 ){ if(p1.a== p2.a)return p1.b > p2.b; return p1.a <p2.a; } int Binary_search(int val){ int l = 1 , r = len ; int res = 0 ; while( l <= r ){ int mid = (l+r)>>1; if( kx[mid] < val){res = mid; l = mid +1;} else r = mid - 1 ; } return res; } int main(){ int n ,tx; while(scanf("%d",&n)!=EOF){ for(int i = 0 ; i < n ;++i){scanf("%d %d",&stu[i].a,&stu[i].b);stu[i].index=i+1;path[i] = -1 ;} sort(stu,stu+n,cmp); len = 0; kx[++len] = stu[0].b; for(int i = 1; i < n ;++i ){ if(stu[i].b > kx[len] ){kx[++len] = stu[i].b,path[i] = flage[len-1];flage[len] = i;} else { tx = Binary_search(stu[i].b); if(kx[tx+1] > stu[i].b){ kx[tx+1] = stu[i].b;flage[tx+1] = i;path[i] = flage[tx];} } } printf("%d/n",len); tx = flage[len--]; printf("%d",stu[tx].index); while(len--){ tx = path[tx]; printf(" %d",stu[tx].index); } printf("/n"); } return 0; }

Segment (ural 1078)

http://acm.timus.ru/problem.aspx?space=1&num=1078

这个题目就是给你n个线段有起始点终止点。让你求一个最大的子集，使得子集里面的线段一个能被另外一个完全包含。

按照第一位排序就是个简单的最长下降子序列的。

代码：#include<iostream>#include<algorithm>using namespace std;struct node {int a , b ; int index;}stu[505];int dp[505];int path[505];bool cmp(const struct node p1 , const struct node p2 ){if( p1.a == p2.a )return p1.b<p2.b;return p1.a < p2.a;}int main(){int n ; while(scanf("%d",&n)!=EOF){for(int i = 0 ; i < n ;++i){scanf("%d%d",&stu[i].a,&stu[i].b);dp[i] =1,path[i] = -1 ; stu[i].index = i +1;}sort(stu,stu+n,cmp);for(int i = 1 ; i < n ;++i){int k = - 1 , min = -1; for(int j = 0 ;j < i +1;++j){if( stu[j].b>stu[i].b && dp[j] > min )k = j , min = dp[j] ; }if( k != -1&& dp[i]<min+1){dp[i] = min+1 ;path[i] = k;}}int k = - 1, min = -1 ;for(int i = 0 ; i <n;++i)if( dp[i] > min ){min = dp[i] ; k = i ;}printf("%d/n",dp[k]);printf("%d",stu[k].index);while( path[k] !=-1){k = path[k];printf(" %d",stu[k].index);}printf("/n");}return 0 ;}

LCS

poj 1080 :Human Gene Functions

http://acm.pku.edu.cn/JudgeOnline/problem?id=1080

代码：

#include<iostream>using namespace std;char a[160],b[160];int df[160][160],La,Lb;int we[5][5]={5, -1, -2, -1, -3,-1, 5, -3, -2, -4, -2, -3, 5, -2, -2, -1, -2, -2, 5, -1, -3, -4, -2, -1, -127};int main(){int i,j,n;char c;scanf("%d",&n);while(n--){ scanf("%d",&La);scanf("%c",&c);for(i=0;i<La;i++){scanf("%c",&a[i]);switch(a[i]){case 'A':a[i] = '0';break;case 'C':a[i] = '1';break; case 'G':a[i] = '2';break; case 'T':a[i] = '3';break; }}scanf("%d",&Lb);scanf("%c",&c);for(i=0;i<Lb;i++){scanf("%c",&b[i]);switch(b[i]){case 'A':b[i] = '0';break;case 'C':b[i] = '1';break; case 'G':b[i] = '2';break; case 'T':b[i] = '3';break; }}df[0][0]=0;for(i=1;i<=La;i++)df[i][0]=df[i-1][0]+we[a[i-1]-'0'][4];for(i=1;i<=Lb;i++)df[0][i]=df[0][i-1]+we[4][b[i-1]-'0'];for(i=1;i<=La;i++)for(j=1;j<=Lb;j++){df[i][j]=df[i-1][j-1]+we[a[i-1]-'0'][b[j-1]-'0'];if(df[i][j]<(df[i-1][j]+we[a[i-1]-'0'][4]))df[i][j]=df[i-1][j]+we[a[i-1]-'0'][4];if(df[i][j]<df[i][j-1]+we[4][b[j-1]-'0'])df[i][j]=df[i][j-1]+we[4][b[j-1]-'0'];}printf("%d/n",df[La][Lb]);}return 0;}

poj 1159 :Palindrome

http://acm.pku.edu.cn/JudgeOnline/problem?id=1159

代码：#include<iostream>#include<string>#include<algorithm>using namespace std;short c[5001][5001];int n;int myf(string s1,string s2){int i,j;for(i=0;i<=n;++i)c[i][0]=0;for(i=0;i<=n;++i)c[0][i]=0;for(i=1;i<=n;++i)for(j=1;j<=n;++j){if(s1[i-1]==s2[j-1])c[i][j]=c[i-1][j-1]+1;if(s1[i-1]!=s2[j-1]){if(c[i-1][j]>c[i][j-1])c[i][j]=c[i-1][j];elsec[i][j]=c[i][j-1];}}return 0;}int main(){string s;int i;while(cin>>n){cin>>s;string rs(s);for(i=0;i<5001;++i)for(int j=0;j<5001;++j)c[i][j]=0;reverse(rs.begin(),rs.end());i=myf(s,rs);printf("%d/n",n-c[n][n]);}return 0;}

poj 1458 Common Subsequence

http://acm.pku.edu.cn/JudgeOnline/problem?id=1458

代码：#include<iostream>#include<string>using namespace std;const int MAX(500);int c[MAX][MAX];int LCS(string s1,string s2){int i,j;int L1=s1.size();int L2=s2.size();for(i=0;i<L1;++i)c[i][0]=0;for(j=0;j<L2;++j)c[0][j]=0;for(i=0;i<L1;++i)for(j=0;j<L2;++j){if(s1[i]==s2[j]){c[i][j]=c[i-1][j-1]+1;}else{if(c[i][j-1]>c[i-1][j])c[i][j]=c[i][j-1];elsec[i][j]=c[i-1][j];}}return c[L1-1][L2-1];}int main(){string s1,s2;while(cin>>s1>>s2){printf("%d/n",LCS(s1,s2));}return 0;}

poj 2192:Zipper

http://acm.pku.edu.cn/JudgeOnline/problem?id=2192

代码

以上是POJ上最LCS题目，可以拿来练手。

花店橱窗布置（IOI99）

poj : 1157 LITTLE SHOP OF FLOWERS

http://acm.pku.edu.cn/JudgeOnline/problem?id=1157

#include<iostream>

using namespace std;

int main()

{

int Map[110][110];

int dp[110][110];

int f,v,i,j,k;

scanf("%d%d",&f,&v);

for(i=1;i<=f;i++)

for(j=1;j<=v;j++)

scanf("%d",&Map[i][j]);

for(i=0;i<110;i++)

for(j=0;j<110;j++)

dp[i][j]=f*(-50);

for(i=1;i<=v;i++)

dp[1][i]=Map[1][i];

for(i=2;i<=f;i++)

for(j=i;j<=v;j++)

{

for(k=i-1;k<j;k++)

{

if(dp[i-1][k]+Map[i][j]>dp[i][j])

dp[i][j]=dp[i-1][k]+Map[i][j];

}

k=dp[f][f];

for(i=f+1;i<=v;i++)

if(dp[f][i]>k)

k=dp[f][i];

printf("%d/n",k);

system("pause");

return 0;

}