最近在学习DP，现在把我这几天AC的题目整理总结一下~
DP在很多时候其实也就是变种的递归，其和递归的区别就在于DP将每次递归地中间结果都存储起来了，避免了常规递归过程中大量的重复计算，从而大大优化的算法的执行效率。
提到DP，就不得不提一下其非常重要的一个组成部分，状态转换方程。在DP的求解过程中，会有很多的中间结果，我们将这些中间结果所构成的集合称之为状态，因而DP的求解也是从问题的初始状态转换为最终状态的一个过程。那么DP的递归过程如何控制呢，这里就有了状态转换方程。该方程可以引导当前的状态转向下一个状态。
由于DP问题的多样性，我们很难找到一个普适的状态转换方程来解决所有的问题。因此，我们需要积累相关的经验，掌握多种具有代表性的问题求解方式。而当以后遇到相似问题时，我们可以将改问题规约到我们熟悉的某类典型问题上，从而求解之。
ok，闲话说到这儿，上题：http://acm.hdu.edu.cn/showproblem.php?pid=1257
//-----来点儿题外话，杭电最近开放了DIY板块，在这个板块中大家可以自己选择contest，也可以整理专题强化训练，而hdu1257 则是我最近参与的DP专题http://acm.hdu.edu.cn/diy/contest_show.php?cid=19045 里的第1014题）
/* 改问题乍看起来 觉得是求最长非增子序列的个数的问题 由于最长非增子序列是经典的DP问题 因此会进入误区，递归调用LICS
* 我们如果把问题反过来 假设dp[i]为当前导弹所能达到的最远距离， 如果下一个高度 a[j]>a[i] 则该导弹必定不能被当前导弹命中 导弹系统的个数需要增加一个
* 如果我们仔细把后一个问题分析一下，发现该问题变成了典型的求最长上升子序列LCS问题了
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
int a[30001],dp[30001];
int n,i,inp,j,Max;
int main()
{
while(scanf("%d",&n)!=EOF && n)
{
Max=0;
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
dp[i]=1;
}
for(i=0;i<n;i++)
{
for(j=0;j<i;j++)
if(a[i]>=a[j] && dp[j]+1>dp[i])
dp[i]=dp[j]+1;
if(dp[i]>Max)
Max=dp[i];
}
printf("%d\n",Max);
}
return 0;
}