文档介绍：线性动规
LIS类型DP
【例题1】:最长不下降序列1078
Description:
设有整数序列b1,b2,b3,……,bm, 若存在i1< i2 <i3 <……<in,且bi1<bi2<bi3……<bin, 则称b1,b2,b3,……,bn,中有长度为N的不下降序列bi1,bi2,bi3,……,bin。求序列b1,b2,b3,……,bm中最大不下降序列的长度。
Input:
第一行为一个数n,表示有n个数,第二行为n个整数序列;
Output:
第一行为最大长度,第二行为满足长度的序列
Sample Input
14
13 7 9 16 38 24 37 18 4 19 21 22 63 15
Sample Output
8
7 9 16 18 19 21 22 63
【试题分析】
1、阶段和状态:
f[i]:表示以a[i]为最后一个数字的最长不下降序列的最大长度;
阶段i表示前i个数,由于每个阶段只有一个状态,所以用一维数组表示;
2、状态转移方程:
初始化:f[i]=1;
f[i]=max{f[j]+1,j<i且a[j]<=a[i]}
answer=max{f[i]};(1<=i<=n)
初始化:
i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
a[i]
13
7
9
16
38
24
37
18
4
19
21
22
63
15
f[i]
1
1
1
1
1
1
1
1
1
1
1
1
1
1
pre[i]
0
0
0
0
0
0
0
0
0
0
0
0
0
0
计算过程:
i
1
2
3
4
5
6
7
8
9
10
11
12
13
14
a[i]
13
7
9
16
38
24
37
18
4
19
21
22
63
15
f[i]
1
1
2
3
4
4
5
4
1
5
6
7
8
3
pre[i]
1
2
2
3
4
4
6
4
9
8
10
11
12
3
3、核心子程序:
说明
数组p[i]记录第i个数前一个结点下标。
void out(int pre[],int a[],int n) //递归输出序列
{ if (pre[n]==n){cout<<a[n]<<" ";return;}
out(pre,a,pre[n]);
cout<<a[n]<<" ";
}
int main()
{ int a[100],f[100],pre[100],i,j,n,max;
cin>>n;
for(i=1;i<=n;i++)
{cin>>a[i];f[i]=1;pre[i]=i;}//初始化
for(i=2;i<=n;i++)
for(j=1;j<i;j++)
if(a[j]<=a[i]&&f[j]+1>f[i]){f[i]=f[j]+1;pre[i]=j;}
max=1;
for(i=1;i<=n;i++)
if(f[i]>f[max])max=i;
cout<<f[max]<<endl;
out(pre,a,max);
return 0;
}
//其中数组pre[i]记录第i个数前一个结点下标。
【例题2】渡轮问题1373
Description
有一个国家被一条河划分为南北两部分,在南岸和北岸总共有N对城镇,每一城镇在对岸都有唯一的友好城镇。任何两个城镇都没有相同的友好城镇。每一对友好城镇都希望有一条航线来往。于是他们向政府提出了申请。由于河终年有雾。政府决定不允许有任两条航线交叉(如果两条航线交叉,将有很大机会撞船)。
你的任务是写一个程序来帮政府官员决定他们应拨款兴建哪些航线以使得没有出现交叉的航线最多。
Input
第一行一个整数N(1 <= N <= 1000),表示分布在河两岸的城镇对数。
接下来的N行每行有两个由空格分隔的正数C,D ( C、D<=10^9 ),描述每一对友好城镇沿着河岸与西边境线的距离,C表示北岸城镇的距离而D表示南岸城镇的距离。在河的同一边,任何两个城镇的位置都是不同的。
Output
在安全条件下能够开通的最大航线数目。
Sample Input
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2
Sample Output
4
【试题分析】:
1、阶段和状态:题目粗略一看,不