hdu 1160 FatMouse's Speed (dp---最长有序子序列）

动态规划使用范围：（http://baike.baidu.com/view/28146.htm）

任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。 　　

1.最优化原理（最优子结构性质） 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。 　　

2.无后效性 将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。 　　

3.子问题的重叠性 动态规划将原来具有指数级复杂度的搜索算法改进成了具有多项式时间的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。 动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

动态规划思想：

       如果各个子问题不是独立的，不同的子问题的个数只是多项式量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是，用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。

时间复杂度为O(n^2)，算法原理：

数组a[]为待处理数组

f[]用于记录a[]数组中，以对应位置数据为结尾的最长有序序列长度

p[]用于记录a[]数组中，以对应位置数据为结尾的前一个数据位置

使用position记录最大长度位置

以a[]={1,4,7,2,5,8,3,6,9}，计算最长递增有序子序列为例

初始化f[]={1, 1, 1, 1, 1, 1, 1,1,1}，p[]={0,1,2,3,4,5,6,7,8}

计算f[i]时，f[i]=max(f[j]+1) ,(其中，a[i]>a[j],i>j>=0)，意思是以a[i]为结尾，找出在a[i]前比a[i]小的数据中以该数据为结尾的最大有序子序列长度max(f[j])，则以a[i]结尾的最大有序子序列长度为max(f[j])+1。计算同时定义p[i]=j，标志a[i]为结尾的最长子序列的前一个数据a[j]的位置。同时判断此时最大长度a[i]是否比当前最大长度max大，如果a[i]更大则更新position

a[]={1,4,7,2,5,8,3,6,9}

i=0   f[]={1,1,1,1,1,1,1,1,1},  p[]={0,1,2,3,4,5,6,7,8}

i=1   f[]={1,2,1,1,1,1,1,1,1},  p[]={0,0,2,3,4,5,6,7,8}  4>1，所以最大长度为2，position=1

i=2   f[]={1,2,3,1,1,1,1,1,1},  p[]={0,0,1,3,4,5,6,7,8}  7>4,7>1 其中4结尾的长度为2，所以最大长度为3，position=2

i=3   f[]={1,2,3,2,1,1,1,1,1},  p[]={0,0,1,0,4,5,6,7,8}  2>1 所以最大长度为2

i=4   f[]={1,2,3,2,3,1,1,1,1},  p[]={0,0,1,0,1,5,6,7,8}  5>1,5>4,5>2,其中以4结尾的长度为2，所以最大长度为3

i=5   f[]={1,2,3,2,3,4,1,1,1},  p[]={0,0,1,0,1,2,6,7,8}  8比前面的数据都大，所以最大长度为4，position=5

i=6   f[]={1,2,3,2,3,4,3,1,1},  p[]={0,0,1,0,1,2,3,7,8}  3>1,3>2,其中以2结尾的长度为2，所以最大长度为3

i=7   f[]={1,2,3,2,3,4,3,4,1},  p[]={0,0,1,0,1,2,3,4,8}  6>1,6>4,6>2,6>5,6>3,其中以5结尾长度为3，所以最大长度为4

i=8   f[]={1,2,3,2,3,4,3,4,5},  p[]={0,0,1,0,1,2,3,4,5}  9比前面数据都大，所以最大长度为5，position=8

在对所有a中元素循环过后，通过max记录下最后数据位置，以及p记录的前一个数据的位置，可以递归求出LIS

代码如下：

#include<stdio.h>

int a[10000]={0};
int f[10000]={0};
int p[10000]={0};
int max=0;
int position =0;
void compare(int n){
	for(int i=0; i<n; i++){
		for(int j=0; j<i; j++){
			if(a[i]>a[j]){
				if(f[i]<f[j]+1){
					f[i]=f[j]+1;
					p[i]=j;
					if(f[i]>max){
						postiion=i;
						max = f[i];
					}
				}
			}
		}
	}
}

void printLIS(int position){		
	if(p[position]==position){
		printf("%d",a[position]);
		return;
	}
	printLIS(p[position]);
	printf(" %d",a[position]);
}

void main(){
	int n;
	max =0;
	position = 0;
	scanf("%d",&n);
	for(int i=0; i<n; i++){
		scanf("%d",&a[i]);
		f[i]=1;
		p[i]=i;
	}
	compare(n);
	printLIS(position);
	printf("\n");
}

p[i]=i;采用的打印方案方法是递归(dfs)。

其实也可以初始化为p[i]=0;这里很灵活~

下面是hdu 1160~代码

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>

using namespace std;

struct mice
{
    int w,s;
    int id;
}m[1010];
int dp[1010],pre[1010];
vector<int> ans;

bool cmp(mice x,mice y)
{
    if(x.w==y.w)
        return x.s>y.s;
    return x.w<y.w;
}

int main()
{
    int n=0,r,tmp;
    while(scanf("%d%d",&m[n].w,&m[n].s)!=EOF)
    {
        m[n].id=n+1;
        dp[n]=1;
        pre[n]=0;
        n++;
    }
    sort(m,m+n,cmp);
    ans.clear();
    int maxl=-1,idm;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(m[j].s>m[i].s && m[j].w<m[i].w && dp[j]+1>dp[i])
            {
                dp[i]=dp[j]+1;
                pre[i]=j;
                if(dp[i]>maxl)
                {
                    maxl=dp[i];
                    idm=i;
                }
            }
        }
    }
    int x=dp[idm];
    printf("%d\n",x);
    while(idm)
    {
        ans.push_back(idm);
        idm=pre[idm];
    }
    for(int i=x-1;i>=0;i--)
        printf("%d\n",m[ans[i]].id);
    return 0;
}

部分内容来自：

http://blog.csdn.net/lawrencesgj/article/details/7881851

深表感谢！！

hdu 1160 FatMouse's Speed (dp---最长有序子序列）

原文：http://blog.csdn.net/u012841845/article/details/18399439