第1章 动态规划

LIS模型

怪盗基德的滑翔翼

求某个点i的max（LIS[0， i], LIS(n, i)）
image.png

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

登山

由题意是只能是先上升然后下降
求一个两个LIS和-1的最大值

image.png

如何确定上升的最高点？

没想到这题真的使用了两个数组

  1. #include <iostream>
  2. using namespace std;
  4. const int N = 1010;
  6. int a[N], f[N], g[N];
  8. int main()
  9. {
  10.     int n; cin >> n;
  12.     for (int i=1; i<=n; i++) cin >> a[i];
  14.     for (int i=1; i<=n; i++)
  15.     {
  16.         f[i] = 1;
  17.         for (int j=1; j<i; j++)
  18.         {
  19.             if (a[i] > a[j])
  20.                 f[i] = max(f[i], f[j]+1);
  21.         }
  22.     }
  25.     for (int i=n; i>0; i--)
  26.     {
  27.         g[i] = 1;
  28.         for (int j=n; j>i; j--)
  29.         {
  30.             if (a[i] > a[j])
  31.                 g[i] = max(g[i], g[j]+1);
  32.         }
  33.     }
  35.     int res = 0;
  36.     for (int i=1; i<=n; i++)
  37.         res = max(res, f[i]+g[i]-1);
  39.     cout << res;
  41.     return 0;
  42. }

采用状态机模型的解法

合唱队形

和登山一题一样，只是返回的是n-最大值 求删除最少的人完成队形😀

  1. #include <iostream>
  2. #include <climits> // INT_MAX
  3. using namespace std;
  5. const int N = 110;
  7. int a[N], f[N], g[N];
  9. int main()
  10. {
  11.     int n; cin >> n;
  13.     for (int i=0; i<n; i++) cin >> a[i];
  16.     for (int i=0; i<n; i++)
  17.     {
  18.         f[i] = 1;
  19.         for (int j=0; j<i; j++)
  20.         {
  21.             if (a[i] > a[j]) 
  22.                 f[i] = max(f[i], f[j]+1);
  23.         }
  24.     }
  27.     for (int i=n-1; i>=0; i--)
  28.     {
  29.         g[i] = 1;
  30.         for (int j=n-1; j>i; j--)
  31.         {
  32.             if (a[i] > a[j])
  33.                 g[i] = max(g[i], g[j]+1);
  34.         }
  35.     }
  38.     int res = INT_MAX;
  39.     for (int i=0; i<n; i++)
  40.         res = min(res, n-(f[i]+g[i]-1));
  42.     cout << res;
  44.     return 0;
  45. }

友好城市

本题是属于思路上比较难的题目

image.png
image.png

只要出席那一种逆序，那么就会出现交叉，那么保证是一种递归的上升即可

状态机模型

image.png
将一个点拓展成多个过程

大盗阿福

不能抢连续点店铺
image.png
image.png
image.png
入口在状态机中也是一个很重要点概念

image.png

  1. #include <iostream>
  2. #include <algorithm>
  4. using namespace std;
  6. const int N = 100010;
  8. int n;
  9. int w[N], f[N][2];
  11. int main()
  12. {
  13.     int T;
  14.     scanf("%d", &T);
  15.     while (T -- )
  16.     {
  17.         scanf("%d", &n);
  18.         for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
  20.         for (int i = 1; i <= n; i ++ )
  21.         {
  22.             f[i][0] = max(f[i - 1][0], f[i - 1][1]);
  23.             f[i][1] = f[i - 1][0] + w[i];
  24.         }
  26.         printf("%d\n", max(f[n][0], f[n][1]));
  27.     }
  29.     return 0;
  30. }

股票买卖IV

image.pngimage.png
由于本题有出手次数的限制，状态表示的时候要引入一维来表示

  1. #include <iostream>
  2. #include <cstring>
  3. #include <climits>
  4. using namespace std;
  6. const int N = 100010, K = 110;
  8. int f[N][K][2], w[N];
  10. int main()
  11. {
  12.     int n, k;
  13.     cin >> n >> k;
  15.     for (int i=1; i<=n; i++) cin >> w[i];
  17.     /*条件初始化*/
  18.     memset(f, -0x3f, sizeof f);
  19.     // 出手0次，获利为0
  20.     for (int i=0; i<=n; i++) f[i][0][0] = 0;
  22.     for (int i=1; i<=n; i++)
  23.     {
  24.         for (int j=1; j<=k; j++)
  25.         {
  26.             f[i][j][0] = max(f[i-1][j][0], f[i-1][j][1] + w[i]);
  27.             f[i][j][1] = max(f[i-1][j-1][0]-w[i], f[i-1][j][1]);
  28.         }
  29.     }
  31.     int res = 0;
  32.     for (int i=0; i<=k; i++)
  33.         res = max(res, f[n][i][0]); // 作为一次完整的交易，最有一次肯定是手中无货的
  35.     cout << res;
  37.     return 0;
  38. }

1058. 股票买卖 V

image.png
初始化一定要，否者这里是通不过的

  1.  #include <iostream>
  2.  #include <climits>
  3.  using namespace std;
  5.  const int N = 100010;
  6.  int w[N], f[N][3];
  8.  int main()
  9.  {
  10.      int n; cin >> n;
  12.      for (int i=1; i<=n; i++)
  13.         cin >> w[i];
  15.      // 记住初始化
  16.      f[0][0] = f[0][1] = INT_MIN;
  17.      for (int i=1; i<=n; i++)
  18.      {
  19.          f[i][0] = max(f[i-1][0], f[i-1][2]-w[i]);
  20.          f[i][1] = f[i-1][0] + w[i];
  21.          f[i][2] = max(f[i-1][2], f[i-1][1]);
  22.      }
  24.      cout << max(f[n][1], f[n][2]);
  26.      return 0;
  28.  }

背包问题

487. 金明的预算方案

第4章 高级数据结构

4.1 并查集

  1. 合并两个集合
  2. 查询某个元素的祖宗节点

**维护的两种形式**

  1. 记录每个集合大小 （绑定到根节点）
  2. 每个点到根节点的距离 （绑定到每个元素上）

    食物链 ===》 拓展域

拓展域的并查集有一种枚举的思想在

1250. 格子游戏

image.png
第一次出现环，计算画的次数

本题算简单，需要将二维代码做一个简答的映射

  1. #include <iostream>
  2. using namespace std;
  4. const int N = 40010;
  6. int p[N], m, n;
  8. int get(int x, int y)
  9. {
  10.     return x*n + y;
  11. }
  13. int find(int x)
  14. {
  15.     if (p[x] != x) p[x] = find(p[x]);
  16.     return p[x];
  17. }
  19. int main()
  20. {
  21.     cin >> n >> m;
  23.     for (int i=1; i<n*n; i++) p[i] = i;
  25.     int res = 0;
  27.     for (int i=1; i<=m; i++)
  28.     {
  29.         int x, y;
  30.         char d;
  32.         cin >> x >> y >> d;
  34.         x--, y--;
  35.         int a = get(x, y);
  37.         int b;
  38.         if (d == 'D') b = get(x+1, y); // down
  39.         else b = get(x, y+1); // right
  41.         int pa = find(a), pb = find(b);
  42.         if (pa == pb) 
  43.         {
  44.             res = i;
  45.             break;
  46.         }
  47.         p[pa] = pb; // 合并
  49.     }
  51.     if (!res) puts("draw");
  52.     else cout << res << endl;
  54.     return 0;
  56. }

252. 搭配购买

01背包问题 虽然看着像是一个由依赖的背包问题，实际上是可以将所有的连通块找出来，然后将每个连通块看作一个问题，转化为一个01背包问题

  1. #include <cstring>
  2. #include <iostream>
  3. #include <algorithm>
  5. using namespace std;
  7. const int N = 10010;
  9. int n, m, vol;
  10. int v[N], w[N];
  11. int p[N];
  12. int f[N];
  14. int find(int x)
  15. {
  16.     if (p[x] != x) p[x] = find(p[x]);
  17.     return p[x];
  18. }
  20. int main()
  21. {
  22.     cin >> n >> m >> vol;
  24.     for (int i = 1; i <= n; i ++ ) p[i] = i;
  25.     for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
  27.     while (m -- )
  28.     {
  29.         int a, b;
  30.         cin >> a >> b;
  31.         int pa = find(a), pb = find(b);
  32.         if (pa != pb)
  33.         {
  34.             v[pb] += v[pa];
  35.             w[pb] += w[pa];
  36.             p[pa] = pb;
  37.         }
  38.     }
  40.     // 01背包
  41.     for (int i = 1; i <= n; i ++ )
  42.         if (p[i] == i)
  43.             for (int j = vol; j >= v[i]; j -- )
  44.                 f[j] = max(f[j], f[j - v[i]] + w[i]);
  46.     cout << f[vol] << endl;
  48.     return 0;
  49. }

4.2 树状数组

image.png

image.png