算法提高课整理

1 动态规划

最长上升子序列模型

怪盗基德的滑翔翼

怪盗基德是一个充满传奇色彩的怪盗，专门以珠宝为目标的超级盗窃犯。

而他最为突出的地方，就是他每次都能逃脱中村警部的重重围堵，而这也很大程度上是多亏了他随身携带的便于操作的滑翔翼。

有一天，怪盗基德像往常一样偷走了一颗珍贵的钻石，不料却被柯南小朋友识破了伪装，而他的滑翔翼的动力装置也被柯南踢出的足球破坏了。

不得已，怪盗基德只能操作受损的滑翔翼逃脱。

假设城市中一共有N幢建筑排成一条线，每幢建筑的高度各不相同。

初始时，怪盗基德可以在任何一幢建筑的顶端。

他可以选择一个方向逃跑，但是不能中途改变方向（因为中森警部会在后面追击）。

因为滑翔翼动力装置受损，他只能往下滑行（即：只能从较高的建筑滑翔到较低的建筑）。

他希望尽可能多地经过不同建筑的顶部，这样可以减缓下降时的冲击力，减少受伤的可能性。

请问，他最多可以经过多少幢不同建筑的顶部(包含初始时的建筑)？

输入格式 输入数据第一行是一个整数K，代表有K组测试数据。

每组测试数据包含两行：第一行是一个整数N，代表有N幢建筑。第二行包含N个不同的整数，每一个对应一幢建筑的高度h，按照建筑的排列顺序给出。

输出格式 对于每一组测试数据，输出一行，包含一个整数，代表怪盗基德最多可以经过的建筑数量。

数据范围 1≤K≤100 1≤N≤100 0<h<10000

输入样例：

1
2
3
4
5
6
7
3
8
300 207 155 299 298 170 158 65
8
65 158 170 298 299 155 207 300
10
2 1 3 4 5 6 7 8 9 10

输出样例：

1
2
3
6
6
9

本体求解最长上升子序列问题

  • 向左滑（最长上升子序列）
  • 向右滑（最长下降子序列）
  • 求一个最大值即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n;
int a[N];
int f[N];
int main () 
{
    int T;
    cin >> T;
    while (T--) 
    {
        cin >> n;
        for (int i = 1;i <= n;i++) cin >> a[i];
        int ans1 = 0,ans2 = 0;
        for (int i = 1;i <= n;i++) 
        {
            f[i] = 1;
            for (int j = 1;j < i;j++) 
            {
                if (a[j] < a[i]) f[i] = max (f[i],f[j] + 1);
            }
            ans1 = max (ans1,f[i]);
        }
        for (int i = 1;i <= n;i++) 
        {
            f[i] = 1;
            for (int j = 1;j < i;j++) 
            {
                if (a[j] > a[i]) f[i] = max (f[i],f[j] + 1);
            }
            ans2 = max (ans2,f[i]);
        }
        cout << max (ans1,ans2) <<'\n';
    }
    return 0;
}

登山

五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。

同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。

队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

输入格式 第一行包含整数N，表示景点数量。

第二行包含N个整数，表示每个景点的海拔。

输出格式 输出一个整数，表示最多能浏览的景点数。

数据范围 2≤N≤1000 输入样例：

1
2
8
186 186 150 200 160 130 197 220

输出样例：

1
4

本题思路就是直接用一个最长上升子序列模型和一个最长下降子序列模型即可解决，因为是先求解最长上升子序列，再求最长下降子序列最后进行累加减去一（去重）即可得到答案。

属性:max

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
using namespace std;
const int N = 1010;
int n;
int a[N];
int f[N],g[N];
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++) 
    {
        f[i] = 1;
        for (int j = 1;j < i;j++) 
        {
            if (a[j] < a[i]) f[i] = max (f[i],f[j] + 1);    
        }
    }
    for (int i = n;i >= 1;i--) 
    {
        g[i] = 1;
        for (int j = n;j > i;j--) 
        {
            if (a[i] > a[j]) g[i] = max (g[i],g[j] + 1);   
        }
    }
    int ans = 0;
    for (int i = 1;i <= n;i++) 
        ans = max (ans,f[i] + g[i] - 1); 
    cout << ans << endl;
    return 0;
}

思路二

本题可以使用状态机模型进行思考。

DP分析法：

状态表示:f[i][j]其中j=0/1

  • 当j=0时候就表示向上走了
  • 当j=1时候就表示向下走了
  • 如果当前是上升状态，那么一定是有上升状态转移
  • 如果是下降状态，那么可以由下降状态，和上升状态转移而来 。

f[i][0]=f[i-1][0]+1

f[i][1]=max(f[i-1][0],f[i-1][1])+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,ans = 0;
int a[N],f[N][2];
int main () 
{
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++) 
    {
        f[i][0] = f[i][1] = 1;
        for (int j = 1;j < i;j++) 
        {
            if (a[j] < a[i]) 
                f[i][0] = max (f[i][0],f[j][0]+1);
            else if (a[j] > a[i]) 
                f[i][1] = max (f[i][1],max (f[j][0],f[j][1])+1);
        }
    }
    for (int i = 1;i <= n;i++) 
        ans = max (ans,max (f[i][0],f[i][1]));
    cout << ans << '\n';
    return 0;
}


合唱队列

\(N\) 位同学站成一排，音乐老师要请其中的 \((N-K)\) 位同学出列，使得剩下的 \(K\) 位同学排成合唱队形。      合唱队形是指这样的一种队形：设 \(K\) 位同学从左到右依次编号为 \(1，2…，K\)，他们的身高分别为 \(T_1，T_2，…，T_K\)，  则他们的身高满足T1<…<Ti>Ti+1>…>TK(1≤i≤K)

你的任务是，已知所有 \(N\) 位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

本题与登山一题几乎一致，只需要计算去掉的人即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;
const int N = 1010;
int n;
int a[N];
int f[N],g[N];
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++) {
        f[i] = 1;
        for (int j = 1;j < i;j++) {
            if (a[j] < a[i]) f[i] = max (f[i],f[j] + 1);
        }
    }
    for (int i = n;i >= 1;i--) {
        g[i] = 1;
        for (int j = n;j > i;j--) {
            if (a[i] > a[j]) g[i] = max (g[i],g[j] + 1);
        }
    }
    int ans = 0;
    for (int i = 1;i <= n;i++) ans = max (ans,f[i] + g[i] - 1);
    cout << n - ans << '\n';    //注意是n-ans
    return 0;
}

友好城市

Palmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。 北岸的每个城市有且仅有一个友好城市在南岸，而且不同城市的友好城市不相同。 每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。 编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。

本题的做法就是先对一边进行排序，然后求解另外一边的最长上升子序列即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=5020;
int n;
PII a[N];
int f[N];
int ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].first>>a[i].second;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
    {
    f[i]=1;
    for(int j=1;j<i;j++)
    {
        if(a[j].second<a[i].second)
        {
            f[i]=max(f[i],f[j]+1);
        }
    }
    ans=max(ans,f[i]);
    }
    cout<<ans<<'\n';
    return 0;
}

最大上升子序列和

一个数的序列 \(b_i\)，当 \(b_1<b_2<…<b_S\) 的时候，我们称这个序列是上升的。 对于给定的一个序列(\(a_1,a_2,…,a_N\))，我们可以得到一些上升的子序列(\(a_{i_1},a_{i_2},…,a_{i_K}\))，这里\(1≤i_1<i_2<…<i_K≤N\)。 比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。 这些子序列中和最大为18，为子序列(1,3,5,9)的和。 你的任务，就是对于给定的序列，求出最大上升子序列和。 注意，最长的上升子序列的和不一定是最大的，比如序列(100,1,2,3)的最大上升子序列和为100，而最长上升子序列为(1,2,3)。

\(\text{DP}\)分析法： 状态表示：\(f_{i}\)

\(f_i\) 表示以第\(i\)个数为结尾的最长上升子序列和

状态计算： 我们选第\(j\)个数，那么对应的就是\(f_j+a_i\) 所以状态转移方程就是\(f_i=\underset{j \in[1,i-1]}\max\lbrace f_j+a_i\rbrace\)

初始化：

初始\(\underset{1\le i \le n}{f_i}=a_i\)

答案：

根据定义，由于每一个数都有可能成为最长上升子序列的最后一个数，所以答案就是\(\underset{1\le i\le n}\max \lbrace f_i \rbrace\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int a[N];
int f[N];
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) 
        cin >> a[i];
    int ans = 0;
    for (int i = 1;i <= n;i++) 
    {
        f[i] = a[i];
        for (int j = 1;j < i;j++) 
        {
            if (a[j] < a[i]) f[i] = max (f[i],f[j] + a[i]);
        }
        ans = max (ans,f[i]);
    }
    cout << ans << '\n';
    return 0;
}

拦截导弹

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。 但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。 某天，雷达捕捉到敌国的导弹来袭。 由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。 输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

第一个问题就是求解最长不上升子序列。

第二个问题就是一个贪心问题，从前到后每个数依次放入不上升子序列，如果现有的现有的子序列结尾都小于当前数，创建新序列；将当前数放到子序列结尾大于等于它的最小的子序列后面。

这个贪心结果显然正确。

然后由于这个求解与最长上升子序列数组一致，因此问题转化为求解最长上升子序列。

最多拦截导弹数是最长不上升子序列；配备最少系统数，最长上升子序列的个数（Dilworth 定理）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n = 0;
int a[N],f[N];
int main () {
    while (cin >> a[n + 1]) 
        n++;
    int ans = 0;
    for (int i = 1;i <= n;i++) 
    {
        f[i] = 1;
        for (int j = 1;j < i;j++) 
        {
            if (a[j] >= a[i]) 
                f[i] = max (f[i],f[j]+1);
        }
        ans = max (ans,f[i]);
    }
    cout << ans <<'\n';
    ans = 0;
    for (int i = 1;i <= n;i++) 
    {
        f[i] = 1;
        for (int j = 1;j < i;j++) 
        {
            if (a[j] < a[i]) 
                f[i] = max (f[i],f[j]+1);
        }
        ans = max (ans,f[i]);
    }
    cout << ans <<'\n' ;
    return 0;
}

导弹防御系统

为了对抗附近恶意国家的威胁，\(R\) 国更新了他们的导弹防御系统。 一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。 例如，一套系统先后拦截了高度为 \(3\) 和高度为 \(4\) 的两发导弹，那么接下来该系统就只能拦截高度大于 \(4\) 的导弹。 给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

对于给出样例，最少需要两套防御系统。 一套击落高度为 \(3,4\) 的导弹，另一套击落高度为 \(5,2,1\) 的导弹。

本题相比上一题多了一个下降的导弹系统，因此在贪心时候我们并不知道是要放在上升子序列还是下降子序列，因此我们需要进行暴搜，搜索所有可能的状态。

同时n的范围提示我们进行剪枝，后面我们会专门学习，这里只需要用一个答案的最优化进行剪枝即可。

在dfs时候切记要恢复现场。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<bits/stdc++.h>
using namespace std;
const int N=60;
int n;
int a[N];
int ans;
int up[N],down[N];
void dfs(int u,int up_cnt,int down_cnt)
{
if(up_cnt+down_cnt>=ans)
{
    return ;
}
if(u>n)
{
    ans=up_cnt+down_cnt;
}
int k=1;
while(k<=up_cnt&&up[k]>=a[u])
{
    k++;
}
int temp=up[k];//为了恢复现场
up[k]=a[u];
if(k<=up_cnt)
{
    dfs(u+1,up_cnt,down_cnt);
}
else
{
    dfs(u+1,up_cnt+1,down_cnt);
}
up[k]=temp;
k=1;
while(k<=down_cnt&&down[k]<=a[u])
{
    k++;
}
temp=down[k];
down[k]=a[u];
if(k<=down_cnt)
{
    dfs(u+1,up_cnt,down_cnt);
}
else
{
    dfs(u+1,up_cnt,down_cnt+1);
}
down[k]=temp;
}
int main()
{
    while(cin>>n,n)
    {
for(int i=1;i<=n;i++)
{
    cin>>a[i];
}
ans=n;
dfs(1,0,0);
cout<<ans<<'\n';
    }
    return 0;
}

最长公共上升子序列

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。 小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。 小沐沐说，对于两个数列 \(A\) 和 \(B\)，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。 奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。 不过，只要告诉奶牛它的长度就可以了。 数列 \(A\) 和 \(B\) 的长度均不超过 \(3000\)。

思路：

状态表示：f[i][j]表示考虑a中前i 个数，b中前j个数，并以b[j]结尾的长度

\(f_{i,j} = \underset{k\in [0,j-1],a[i]=b[j],b_k<a_i}\max{\{f_{i-1,j},f_{i-1,k}+1\}}\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
const int N = 3010;
int n;
int a[N],b[N];
int f[N][N];
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++) cin >> b[i];
    for (int i = 1;i <= n;i++) 
    {
        for (int j = 1;j <= n;j++) 
        {
            f[i][j] = f[i - 1][j];
            if (a[i] == b[j]) 
            {
                f[i][j] = max (f[i - 1][j],1);
                for (int k = 1;k <= j - 1;k++) 
                {
                    if (b[k] < a[i]) 
                        f[i][j] = max (f[i][j],f[i][k] + 1);
                }
            }
        }
    }
    int ans = 0;
    for (int i = 1;i <= n;i++) 
        ans = max (ans,f[n][i]);
    cout << ans << '\n';
    return 0;
}

优化

由于f[i][k]的含义就是前 j-1个数字中小于a[i]中的f[i-1][j]中的最大值，实际上不需要单独去处理，可以用一个变量不断更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
using namespace std;
const int N = 3010;
int n;
int a[N],b[N];
int f[N][N];
int main () {
    cin >> n;
    for (int i = 1;i <= n;i++) 
        cin >> a[i];
    for (int i = 1;i <= n;i++) 
        cin >> b[i];
    for (int i = 1;i <= n;i++)
    {
        int maxv = 1;
        for (int j = 1;j <= n;j++) 
        {
            f[i][j] = max (f[i][j],f[i - 1][j]);
            if (a[i] == b[j]) 
                f[i][j] = max (f[i][j],maxv);
            if (b[j] < a[i]) 
                maxv = max (maxv,f[i - 1][j] + 1);
        }
    }
    int ans = 0;
    for (int i = 1;i <= n;i++) 
        ans = max (ans,f[n][i]);
    cout << ans <<'\n';
    return 0;
}