• 算法竞赛备赛进阶之最大上升子序列训练

    回顾前文的最大上升子序列问题

    我们是采用了闫氏DP分析法

    动态规划：

    1. 状态表示f[i]

      1. 集合：所有以a[i]结尾的严格单调上升子序列

      2. 属性：Max/Min/数量

    2. 状态计算

      1. 划分依据：最后一个不同的点

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

    贪心算法章节也有相应的解法

    1.怪盗基德的滑翔翼

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

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

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

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

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

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

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

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

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

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

    1. #include
    2. #include
    3. ​
    4. using namespace std;
    5. ​
    6. const int N = 1010;
    7. ​
    8. int n;
    9. int a[N], f[N];
    10. ​
    11. int main()
    12. {
    13.     int T;
    14.     scanf("%d", &T);
    15.     
    16.     while(T--)
    17.     {
    18.         scanf("%d", &n);
    19.         for(int i = 1;i <= n; i++)
    20.             scanf("%d", &a[i]);
    21.         
    22.         //正向求解LIS问题
    23.         int res = 0;
    24.         for(int i = 1;i <= n; i++)
    25.             if(a[i] > a[j])
    26.                 f[i] = max(f[i], f[j] + 1);
    27.         res = max(res, f[i]);
    28.         
    29.         //反向求解LIS问题
    30.         for(int i = n; i; i--)
    31.         {
    32.             f[i] = 1;
    33.             for(int j = n;j > i; j--)
    34.                 if(a[i] > a[j])
    35.                     f[i] = max(f[i], f[j] + 1);
    36.             
    37.             res = max(res, f[i]);
    38.         }
    39.         
    40.         printf("%d\n", res);
    41.     }
    42.     
    43.     return 0;
    44. }

    2.登山

    五一到了，ACM队组织大家去登山观光，队员们发现山上一个有N NN个景点，并给定各个景点的海拔，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。队员们希望在满足上面条件的同时，尽可能多的浏览景点，求最多可能浏览的景点数。

    条件1：按照编号递增的顺序来浏览 => 必须是子序列

    条件2：相邻两个经典不相等

    条件3：一旦开始下降，就不能上升了

    目标：求最多能浏览多少景点

    目标：所有形状是上面这种的子序列长度的最大值

    uTools_1690894260589

    目标求出第k类最大的长度

    1. #include
    2. #include
    3. ​
    4. using namespace std;
    5. ​
    6. const int N = 1010;
    7. ​
    8. int n;
    9. int a[N];
    10. int f[N], g[N];
    11. ​
    12. int main()
    13. {
    14.     scanf("%d", &n);
    15.     
    16.     for(int i = i;i <= n; i++)
    17.         scanf("%d", &a[i]);
    18.     
    19.     for(int i = 1;i <= n; i++)
    20.     {
    21.         f[i] = 1;
    22.         for(int j = 1;j <= i; j++)
    23.             if(a[i] > a[j])
    24.                 f[i] = max(f[i], f[j] + 1);
    25.     }
    26.     
    27.     for(int i = n; i; i--)
    28.     {
    29.         g[i] = 1;
    30.         for(int j = n;j > i; j--)
    31.             if(a[i] > a[j])
    32.                 g[i] = max(g[i], g[j] + 1);
    33.     }
    34.     
    35.     int res = 0;
    36.     for(int i = 1;i <= n; i++)
    37.         res = max(res, f[i] + g[i] - 1);
    38.     
    39.     printf("%d\n", res);
    40.     
    41.     return 0;
    42. }

    3.合唱队形

    N 位同学站成一排，音乐老师要请其中的 (N−K) 位同学出列，使得剩下的 K 位同学排成合唱队形。     

    合唱队形是指这样的一种队形：设 KK 位同学从左到右依次编号为 1，2…，K，他们的身高分别为 T1，T2，…，TK，则他们的身高满足 T1<…< Ti >Ti+1>…>TK(1≤i≤K)。  

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

    1. #include
    2. #include
    3. ​
    4. using namespace std;
    5. ​
    6. const int N = 110;
    7. ​
    8. int n;
    9. int a[N];
    10. int f[N], g[N];
    11. ​
    12. int main()
    13. {
    14.     scanf("%d", &n);
    15.     for(int i = 1;i <= n; i++)
    16.         scanf("%d", &a[i]);
    17.     
    18.     for(int i = 1;i <= n; i++)
    19.     {
    20.         f[i] = 1;
    21.         for(int j = 1;j <= i; j++)
    22.             if(a[i] > a[j])
    23.                 f[i] = max(f[i], f[j] + 1);
    24.     }
    25.     
    26.     for(int i = n; i; i--)
    27.     {
    28.         g[i] = 1;
    29.         for(int j = n;j > i; j--)
    30.             if(a[i] > a[j])
    31.                 g[i] = max(g[i], g[j] + 1);
    32.     }
    33.     
    34.     int res = 0;
    35.     for(int i = 1;i <= n; i++)
    36.         res = max(res, f[i] + g[i] - 1);
    37.     
    38.     printf("%d\n", n - res);
    39.     return 0;
    40. }

    4.友好城市

    Pmia国有一条横贯东西的大河，河有笔直的南北两岸，岸上各有位置各不相同的N个城市。

    北岸的每个城市有且仅有一个友好城市在南岸，而目不同城市的友好城市不相同。

    每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市，但是由于河上雾太大，政府决定避免任意两条航道交叉，以避免事故。

    编程帮助政府做出一些批准和拒绝申请的决定，使得在保证任意两条航线不相交的情况下，被批准的申请尽量多。

    条件1：每个城市上只能建立一座桥

    条件2：所有的桥与桥之间不能相交

    1. #include
    2. #include
    3. ​
    4. using namespace std;
    5. ​
    6. typedef pair<int, int> PII;
    7. ​
    8. const int N = 5010;
    9. ​
    10. int n;
    11. PII q[N];
    12. int f[N];
    13. ​
    14. int main()
    15. {
    16.     scanf("%d", &n);
    17.     for(int i = 0;i < n; i++)
    18.         scanf("%d%d", &q[i].first, &q[i].second);
    19.     
    20.     sort(q, q + n);
    21.     
    22.     int res = 0;
    23.     for(int i = 0;i < n; i++)
    24.     {
    25.         f[i] = 1;
    26.         for(int j = 0;j < i; j++)
    27.             if(q[i].second > q[j].second)
    28.                 f[i] = max(f[i], f[j] + 1);
    29.         
    30.         res = max(res, f[i] + 1);
    31.     }
    32.     
    33.     printf("%d\n", res);
    34.     
    35.     return 0;
    36. }

    5.最大上升子序列和

    一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ...,aN)，我们可以得到一些上升的子序列(ai1, ai2, ..., aiK)，这里1 <= i1 < i2 < ... < iK <= 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)

    1. #include
    2. #include
    3. ​
    4. using namespace std;
    5. ​
    6. const int N = 1010;
    7. ​
    8. int n;
    9. int a[N], f[N];
    10. ​
    11. int main()
    12. {
    13.     scanf("%d", &n);
    14.     for(int i = 1;i <= n; i++) scanf("%d", &a[i]);
    15.     
    16.     for(int i = 1;i <= n; i++)
    17.     {
    18.         f[i] = 1;
    19.         for(int j = 1;j < i; j++)
    20.             if(a[i] > a[j])
    21.                 f[i] = max(f[i], f[j] + a[i]);
    22.     }
    23.     
    24.     int res = 0;
    25.     for(int i = 1;i <= n; i++) res = max(res, f[i]);
    26.     
    27.     printf("%d\n", &res);
    28.     return 0;
    29. }

    6.拦截导弹

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

    选择1：接在现有的某个子序列之后

    选择2：创建一个新系统

    贪心流程：从前往后扫描每个数，对于每个数

    情况1：如果现有的子序列的结尾都小于当前的数，则创建新子序列

    情况2：将当前数放到结尾大于等于它的最小子序列后面

    如何证明两个数相等：A≤B B≤A

    A表示贪心算法得到的序列个数；B表示最优解；B≤A，A≤B，调整法

    假设最优解对应的方案和当前方案不同

    找到第一个不同的数。贪心法和最优解

    389 207 155 300 299 170 158 65

    1. #include
    2. #include
    3. ​
    4. using namespace std;
    5. ​
    6. const int N = 1010;
    7. ​
    8. int n;
    9. int q[N];
    10. int f[N], g[N];
    11. ​
    12. int main()
    13. {
    14.     while(cin >> q[n]) n++;
    15.     
    16.     int res = 0;
    17.     for(int i = 0;i < n; i++)
    18.     {
    19.         f[i] = 1;
    20.         for(int j = 0;j < i; j++)
    21.             if(q[j] > q[i])
    22.                 f[i] = max(f[i], f[j] + 1);
    23.         res = max(res, f[i]);
    24.     }
    25.     
    26.     cout << res << endl;
    27.     
    28.     int cnt = 0;
    29.     for(int i = 0;i < n; i++)
    30.     {
    31.         int k = 0;
    32.         while(k < cnt && g[k] < q[i]) k++;
    33.         g[k] = q[i];
    34.         if(k >= cnt) cnt++;
    35.     }
    36.     
    37.     cout << cnt << endl;
    38.     
    39.     return 0;
    40. }

    7.导弹防御系统

    为了对抗附近恶意国家的威胁，RR 国更新了他们的导弹防御系统。

    一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。

    例如，一套系统先后拦截了高度为 3 和高度为 4 的两发导弹，那么接下来该系统就只能拦截高度大于 4 的导弹。

    给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

    1. #include
    2. using namespace std;
    3. ​
    4. using namespace std;
    5. ​
    6. const int N = 55;
    7. ​
    8. int n;
    9. int q[N];
    10. int up[N], down[N];
    11. int ans;
    12. ​
    13. void dfs(int u, int su, int sd)
    14. {
    15.     if(su + sd >= ans) return;
    16.     if(u == n)
    17.     {
    18.         ans = su + sd;
    19.         return;
    20.     }
    21.     
    22.     //情况1：将当前数放到上升序列中
    23.     int k = 0;
    24.     while(k < su && up[k] >= q[u]) k++;
    25.     int t = up[k];
    26.     up[k] = q[u];
    27.     if(k < su) dfs(u + 1, su, sd);
    28.     else dfs(u + 1, su + 1, sd);
    29.     up[k] = t;
    30.     
    31.     //情况2：将当前数放到下降子序列中
    32.     k = 0;
    33.     while(k < sd && down[k] <= q[u]) k++;
    34.     t = down[k];
    35.     down[k] = q[u];
    36.     if(k < sd) dfs(u + 1, su, sd);
    37.     else dfs(u + 1, su, sd + 1);
    38.     down[k] = t;
    39. }
    40. ​
    41. int main()
    42. {
    43.     while(cin >> n, n)
    44.     {
    45.         for(int i = 0;i < n; i++)
    46.             cin >> q[i];
    47.         
    48.         ans = n;
    49.         dfs(0, 0, 0);
    50.         
    51.         cout << ans << endl;
    52.     }
    53. }

    8.最长公共子序列

    熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。

    小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。

    小沐沐说，对于两个数列 A 和 B，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。

    奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。

    不过，只要告诉奶牛它的长度就可以了。

    数列 A 和 B 的长度均不超过 3000。

    1. #include
    2. #include
    3. ​
    4. using namespace std;
    5. ​
    6. const int N = 3010;
    7. ​
    8. int n;
    9. int a[N], b[N];
    10. int g[N][N];
    11. int f[N][N];
    12. ​
    13. int main()
    14. {
    15.     scanf("%d", &n);
    16.     for(int i = 1;i <= n; i++) scanf("%d", &a[i]);
    17.     for(int i = 1;i <= n; i++) scanf("%d", &b[i]);
    18.     
    19.     for(int i = 1;i <= n; i++)
    20.     {
    21.         g[i][0] = 1;
    22.         for(int j = 1;j <= n; j++)
    23.         {
    24.             f[i][j] = f[i - 1][j];
    25.             if(a[i] == b[j]) f[i][j] = max(f[i][j], g[i][j - 1]);
    26.             g[i][j] = g[i][j - 1];
    27.             if(b[j] < a[i]) g[i][j] = max(g[i][j], f[i][j] + 1);
    28.         }
    29.     }
    30.     
    31.     int res = 0;
    32.     for(int i = 1;i <= n; i++) res = max(res, f[n][i]);
    33.     
    34.     printf("%d\n", res);
    35.     
    36.     return 0;
    37. }

    改进：

    1. #include
    2. #include
    3. using namespace std;
    4. ​
    5. const int N = 3010;
    6. ​
    7. int n;
    8. int a[N], b[N];
    9. int f[N][N];
    10. ​
    11. int main()
    12. {
    13.     scanf("%d", &n);
    14.     for(int i = 1;i <= n; i++)
    15.         scanf("%d", &a[i]);
    16.         
    17.     for(int i = 1;i <= n; i++)
    18.         scanf("%d", &b[i]);
    19.         
    20.     for(int i = 1;i <= n; i++)
    21.     {
    22.         int maxv = 1;
    23.         for(int j = 1;j <= n; j++)
    24.         {
    25.             f[i][j] = f[i-1][j];
    26.             if(a[i] == b[j]) f[i][j] = max(f[i][j], maxv);
    27.             if(b[j] < a[i]) maxv = max(maxv, f[i - 1][j] + 1);
    28.         }
    29.     }
    30.         
    31.     int res = 0;
    32.     
    33.     for(int j = 1;j <= n; j++)
    34.         res = max(res, f[n][j]);
    35.         
    36.     printf("%d\n", res);
    37.     return 0;
    38. }

  • 相关阅读:
    MySQL原理和优化
    【Educoder数据挖掘实训】了解数据
    LeetCode题：两数之和-2023/9/11
    c#中webservice的调用
    黄金票据和白银票据
    垃圾回收机制
    【步骤详解】Docker一键部署微服务详细教程
    计算机毕业设计开题报告怎么写丨计算机毕业设计开题报告模板下载（关注博主领取）
    算法刷题打卡第33天：香槟塔
    Meta 开源语音 AI 模型支持 1,100 多种语言
  • 原文地址：https://blog.csdn.net/Williamtym/article/details/134011881