线性动态规划:
- 不用多说，主要应用于求上升子序列，下降子序列等
- 直接看例题：
样例输入：
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;
const int MAX = 1050;
int n, ans;
int f[MAX], a[MAX], pre[MAX], en;
//f[i]表示前i个数中的最大上升序列
//pre[]用来打印路径
void putout(int x){
if(x == 0) return ;
putout(pre[x]);//递归一直求该序列中的上一个数
printf("%d ",a[x]);
}
int main(){
int x;
while(~scanf("%d",&x)) a[++n] = x;
for(int i=1; i<=n; i++){
f[i] = 1;
for(int j=1; j<i; j++){ //从1到i中比i小的个数
if(a[i]>a[j] and f[i]<f[j]+1){
f[i] = f[j] + 1;
pre[i] = j; //标记，i的前一个数为j;
}
}
if(ans < f[i]){
ans = f[i];
en = i;
}
}
printf("max=%d\n",ans);
putout(en); //递归输出
return 0;
}
经过第一道例题，我们已经了解线性dp的特点以及大致模板了。现在上难度：
样例输入：
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
样例输出：
4
解：
将南岸城市和北岸城市在坐标图中表示出来，将一一对应的两城市连线，容易发现，若连线交叉，则会发生事故。那么我们可以知道按南岸城市坐标从小到大排序，相对应的北岸城市坐标求最大上升序列个数即为答案。
代码实现如下：#include<bits/stdc++.h>
using namespace std;
const int MAX = 5050;
int n, m, tot;
int ans;
int f[MAX], ntos[10050];
int main(){
int x, y, Nmax = 0;
scanf("%d",&n);
for(int i=1; i<=n; i++){
scanf("%d%d",&x, &y);
ntos[x] = y; //表示南岸坐标为x的城市对应的北岸坐标
Nmax = max(Nmax, x); //求出南岸最大坐标
}
//按南岸城市坐标大小依次遍历
for(int i=1; i<=Nmax; i++){
if(ntos[i])
{
int a = ntos[i];
ntos[i] = 0;
ntos[++tot] = a;
}
}
//即可转化为求最大上升序列
for(int i=1; i<=n; i++){
f[i] = 1;
for(int j=1; j<i; j++){
if(ntos[i] > ntos[j]){
f[i] = max(f[i], f[j]+1);
}
}
ans=max(ans, f[i]);
}
printf("%d", ans);
return 0;
}