基本应用：
最长上升子序列：
题目描述
设有由n个不相同的整数组成的数列，记为:b(1)、b(2)、……、b(n)且b(i)<>b(j) (i<>j)，若存在i1<i2<i3< … < ie 且有b(i1)<b(i2)< … <b(ie)则称为长度为e的不下降序列。程
序要求，当原数列出之后，求出最长的上升序列。
例如13，7，9，16，38，24，37，18，44，19，21，22，63，15。例中13，16，18，19，21，22，63就是一个长度为7的不下降序列，同时也有7 ，9，16，18，
19，21，22，63长度为8的不下降序列。
输入格式
只有一行，为若干正整数（最多1000个数）
输出格式
为两行，第一行为最上升序列的长度。 第二行为该序列
样例
样例输入
13 7 9 16 38 24 37 18 44 19 21 22 63 15
样例输出
max=8
7 9 16 18 19 21 22 63
解：板子题，不多解释
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,m,f[1111],a[1111],ans,way[1111],te;
//递归输出路径
void p(int x){
if(x==0)return;
p(way[x]);
cout<<a[x]<<" ";
}
int main(){
while(cin>>n)a[++m]=n;
for(int i=1;i<=m;i++){//遍历每个数
f[i]=1;//最少上升子序列数也是1
for(int j=1;j<i;j++){//看当前数前面的最长上升子序列长度f[j]，如果这个数大于其最大数，则更新此数为f[j]+1
if(a[i]>a[j]&&f[i]<f[j]+1){
f[i]=f[j]+1;
way[i]=j;//记录路径
}
}
if(ans<f[i]){
ans=f[i];//更新ans
te=i;//并找到路径的尾
}
}
cout<<"max="<<ans<<endl;
p(te);
return 0;
}
扩展应用：
拦截导弹简单版：
题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
输入只有一行，为若干个正整数，一次为导弹的高度。
输出格式
第一行为最多能拦截的导弹数；
第二行为要拦截所有导弹最少要配备的系统数
样例
样例输入
389 207 155 300 299 170 158 65
样例输出
6
2
解：这道题虽说是板子，但他让求了系统数，所以—————看解释：
定理
在X中，对于元素a，如果任意元素b，都有a≤b，则称a为极小元。
定理1：令（X,≤）是一个有限偏序集，并令r是其最大链的大小。则X
可以被划分成r个但不能再少的反链。
其对偶定理称为Dilworth定理：
令（X,≤）是一个有限偏序集，并令m是反链的最大的大小。则X可以
被划分成m个但不能再少的链。
虽然这两个定理内容相似，但第一个定理证明要简单一些。此处就只
证明定理1。
证明：设p为最少反链个数
(1)先证明集合X不能划分成小于r个反链。由于r是最大链
C的大小，C中任两个元素都可比，因此C中任两个元素都
不能属于同一反链。所以p>=r（p大于等于r）。
(2)设集合X1＝集合X，A1是X1中的极小元的集合。从X1中
删除A1得到X2。注意到对于X2中任意元素a2，必存在X1中
的元素a1，使得a1<=a2。令A2是X2中极小元的集合，从X2
中删除A2得到X3……，最终会有一个Xk非空而Xk+1为空。
于是A1,A2,…,Ak就是X的反链的划分，同时存在链
a1<=a2<=…<=ak，其中ai在Ai内。由于r是最长链大小，
因此r>=k。由于X被划分成了k个反链，因此r>=k>=p。
(3)因此r=p，定理1得证。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int n,m,f[1111],a[1111],ans,way[1111],te,vis[1111];
int main(){
while(cin>>n)a[++m]=n;
//先正序求最大不下降子序列，即为最多能拦截的导弹数
for(int i=1;i<=m;i++){
f[i]=1;
for(int j=1;j<i;j++){
if(a[i]<=a[j]&&f[i]<f[j]+1){
f[i]=f[j]+1;
}
}
if(ans<f[i]){
ans=f[i];
}
}cout<<ans<<endl;
ans=0;
//求最长下降子序列，由证明得即为最少要配备的系统数
for(int i=1;i<=m;i++){
f[i]=1;
for(int j=1;j<i;j++){
if(a[i]>a[j]&&f[i]<f[j]+1){
f[i]=f[j]+1;
}
}
if(ans<f[i]){
ans=f[i];
}
}cout<<ans;
return 0;
}
变形：
麻烦的聚餐
题目描述
为了避免餐厅过分拥挤，FJ要求奶牛们分3批就餐。
每天晚饭前，奶牛们都会在餐厅前排队入内，按FJ的设想，所有第3批就餐的奶牛排在队尾，队伍的前端由设定为第1批就餐的奶牛占据，中间的位置就归第2批就餐的奶牛了。
由于奶牛们不理解FJ的安排，晚饭前的排队成了一个大麻烦。
第i头奶牛有一张标明她用餐批次D_i(1 <= D_i <= 3)的卡片。虽然所有N(1 <= N <= 30,000)头奶牛排成了很整齐的队伍，但谁都看得出来，卡片上的号码是完全杂乱无章的。
在若干次混乱的重新排队后，FJ找到了一种简单些的方法：奶牛们不动，他沿着队伍从头到尾走一遍，把那些他认为排错队的奶牛卡片上的编号改掉，最终得到一个他想要的每个组中的奶牛都站在一起的队列，例如111222333或者333222111。
哦，你也发现了，FJ不反对一条前后颠倒的队 列，那样他可以让所有奶牛向后转，然后按正常顺序进入餐厅。
你也晓得，FJ是个很懒的人。他想知道，如果他想达到目的，那么他最少得改多少头奶牛卡片上的编号。所有奶牛在FJ改卡片编号的时候，都不会挪位置
输入格式
第1行: 1个整数：N
第2..N+1行: 第i+1行是1个整数，为第i头奶牛的用餐批次D_i
输出格式
第1行: 输出1个整数，为FJ最少要改几头奶牛卡片上的编号，才能让编号变成他设想中的样子
样例
样例输入
5
1
3
2
1
1
样例输出
1
数据范围与提示
【输入说明】
队列中共有5头奶牛，第1头以及最后2头奶牛被设定为第一批用餐，第2头奶牛的预设是第三批用餐，第3头则为第二批用餐。
【输出说明】
如果FJ想把当前队列改成一个不下降序列，他至少要改2头奶牛的编号，一种可行的方案是：把队伍中2头编号不是1的奶牛的编号都改成1。不过，如果FJ选择把第1头奶牛的编号改成3就能把奶牛们的队伍改造成一个合法的不上升序列了。
解：一眼看去，这不就是线性dp的板子题吗，要是这样认为，写出代码后，你会被现实伤的体无完肤，又一眼看去，发现数据范围是n<=30000，这就会让我们n^2的复杂度很难办，限时1s,接近1e9的运算量，直接就是kuku超时。那怎么办呢，观察一下这道题的特点，它的数只有1，2，3。那就好办了。直接换一种思路，把第二层循环直接换成三个数的遍历，推一个新的状态转移方程就行了。如下:
点击查看代码
#include<bits/stdc++.h>
using namespace std;
int f[31111],w[31111],m,n,k[31111][4],l[31111][4],ans;//三个数，k,l第二维开4就够用了
int main(){
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&w[i]);
f[n-i+1]=w[i];//倒序存一遍，一会和正序一起算就行
}
for(int i=1;i<=n;i++){
k[i][1]=k[i-1][1]+(f[i]!=1);//要想把第i个置成1，就需要i前面的全是1，如果自己是1，就不需要变了，否则把自己变成1并把上一个状态+1；
k[i][2]=min(k[i-1][2],k[i-1][1])+(f[i]!=2);//要想把第i个置成2，就需要i前面的不是1就是2，取一个最小值即可，如果自己是2，就不需要变了，否则把自己变成2并把上一个状态+1；
k[i][3]=min(min(k[i-1][2],k[i-1][1]),k[i-1][3])+(f[i]!=3);//要想把第i个置成3，i前就没有限制了，取一个最小值即可，如果自己是3，就不需要变了，否则把自己变成3并把上一个状态+1；
//再倒序遍历一遍即可，和上面一样，一会取一下两种的最小即可
l[i][1]=l[i-1][1]+(w[i]!=1);
l[i][2]=min(l[i-1][2],l[i-1][1])+(w[i]!=2);
l[i][3]=min(min(l[i-1][2],l[i-1][1]),l[i-1][3])+(w[i]!=3);
}
ans=1111111;//要求最小，先把ans赋成一个极大值
//所有情况遍历一遍取最小
for(int i=1;i<=3;i++){
ans=min(ans,min(k[n][i],l[n][i]));
}
cout<<ans;
return 0;
}