首页 algorithm 算法OJ Acwing

# 数字三角形模型

# 方格取数

分析：

  1. 因为要走两次，并且走之后会重新更新为 0，所以让两个同时走

  2. 如果要同时走，就需要四维，如何优化呢？根据观察，因为两者同时走，所以走的步数是一样的，即i1+j1=i2+j2i1+j1=i2+j2，所以可以设置一维是k,k=i1+j1=i2+j2k,k=i1+j1=i2+j2，就优化成了三维

  3. 通过判断i1i1 是否等于i2i2，决定最终要加几次权重

  4. 因为i1,i2i1,i2 都有可能从上或者左来，所以一共有 4 种状态

  5. 状态计算：f(k,i1,i2)=max(f(k−1,i1−1,i2−1),f(k−1,i1−1,i2),f(k−1,i1,i2−1),f(k−1,i1,i2))+w[i][j]f(k,i1,i2)=max(f(k-1,i1-1,i2-1),f(k-1,i1-1,i2),f(k-1,i1,i2-1),f(k-1,i1,i2))+w[i][j]

    （依次表示都从上，i1 从上 i2 从左，i1 从左 i2 从上，都从左）

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
#include <iostream>
#include <cstring>
using namespace std;
const int N = 15;
int f[2 * N][N][N], g[N][N];
int n;
int main()
{
    cin >> n;
    int x, y, z;
    while(cin >> x >> y >> z, x | y | z) g[x][y] = z;
    for(int k = 2; k <= 2 * n; k++)
    {
        for(int i1 = 1; i1 <= n; i1++)
        {
            for(int i2 = 1; i2 <= n; i2++)
            {
                int j1 = k - i1, j2 = k - i2;
                if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
                {
                    int &x = f[k][i1][i2];
                    int t = g[i1][j1];
                    if(i1 != i2) t += g[i2][j2];
                    x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
                    x = max(x, f[k - 1][i1][i2 - 1] + t);
                    x = max(x, f[k - 1][i1 - 1][i2] + t);
                    x = max(x, f[k - 1][i1][i2] + t);
                }
            }
        }
    }
    cout << f[2 * n][n][n];
    return 0;
}

# 传纸条

方格取数是同向一起走，传纸条是相向先后走，为什么所用的代码是一样的呢？

~

既然答案中的 i1 一定不等于 i2，为什么代码中还要写出来呢？

因为不想交的线是由相交的线得到的，所以相交的线是构成最优的必须过程

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 <cstring>
using namespace std;
const int N = 60;
int f[2 * N][N][N], g[N][N];
int n, m;
int main()
{
    cin >> m >> n;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            cin >> g[i][j];
    for(int k = 2; k <= n + m; k++)
    {
        for(int i1 = 1; i1 <= m; i1++)
        {
            for(int i2 = 1; i2 <= m; i2++)
            {
                int j1 = k - i1, j2 = k - i2;
                if(j1 >= 1 && j1 <= n && j2 >= 1 && j2 <= n)
                {
                    int &x = f[k][i1][i2];
                    int t = g[i1][j1];
                    if(i1 != i2) t += g[i2][j2];
                    x = max(x, f[k - 1][i1 - 1][i2 - 1] + t);
                    x = max(x, f[k - 1][i1][i2 - 1] + t);
                    x = max(x, f[k - 1][i1 - 1][i2] + t);
                    x = max(x, f[k - 1][i1][i2] + t);
                }
            }
        }
    }
    cout << f[m + n][m][m];
    return 0;
}

# 最长上升子序列

# 合唱队形

分两步：先求以每个节点为结尾的最长上升子序列，再求以每个节点开始的最长下降子序列；最后相加即可

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
#include <iostream>
using namespace std;
const int N = 110;
int h[N], f[N], uf[N];
int n;
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> h[i];
    for(int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for(int j = 1; j <= n; j++)
            if(h[j] < h[i]) f[i] = max(f[i], f[j] + 1);
    }
    for(int i = n; i >= 1; i--)
    {
        uf[i] = 1;
        for(int j = n; j > i; j--)
            if(h[j] < h[i]) uf[i] = max(uf[i], uf[j] + 1); 
    }
    int ans = 0;
    for(int i = 1; i <= n; i++) ans = max(ans, f[i] + uf[i] - 1);
    cout << n - ans;
    return 0;
}

# 拦截导弹

方法一：

  1. 第一问即求最长不上升子序列的长度
  2. 第二问要求最少有多少个不上升的子序列，可以等价于求最长上升子序列的长度\color{red}{等价于求最长上升子序列的长度}（还不会证明 QAQ）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int w[N], f[N], g[N];
int n = 1;
int ans1, ans2;
int main()
{
    while (cin >> w[n]) n++;
    n -= 1;
    for (int i = 1; i <= n; i++)
    {
        f[i] = 1, g[i] = 1;
        for (int j = 1; j < i; j++)
        {
            if (w[j] >= w[i]) f[i] = max(f[i], f[j] + 1);
            else  g[i] = max(g[i], g[j] + 1);
        }
        ans1 = max(ans1, f[i]);
        ans2 = max(ans2, g[i]);
    }
    cout << ans1 << '\n' << ans2;
    return 0;
}

方法二：（第二问）

  1. 维护一个所有子序列末尾的子弹高度的非递减数组
  2. 如果新的导弹高度高于现在最高的结尾高度，那就新开一个空间放这个导弹
  3. 如果新的导弹高度低于现在最高的结尾高度，找到大于它的最小高度，加在这个的后面，并修改最高高度
  4. 求大于它的最小值，可以使用二分进行优化
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;
const int N = 1010;
int h[N], f[N], g[N];
int n, cnt;
int ans1;
int main()
{
    while(cin >> h[++n]);
    n -= 1;
    //第一问
    for(int i = 1; i <= n; i++)
    {
        f[i] = 1;
        for(int j = 1; j < i; j++)
            if(h[j] >= h[i]) f[i] = max(f[i], f[j] + 1);
            ans1 = max(ans1, f[i]);
    }
    cout << ans1 << '\n';
    //第二问
    g[0] = 0x3f3f3f3f;
    for(int i = 1; i <= n; i++)
    {
        int x = lower_bound(g, g + cnt, h[i]) - g;//找到第一个大于h[i]的地方
        if(x == cnt) g[cnt++] = h[i];
        else g[x] = h[i];
        cnt = max(x, cnt);
    }
    cout << cnt;
    return 0;
}