AcWing 第5讲 动态规划

背包问题

01背包

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
#include <algorithm>
#include <iostream>
// #include <cmath>
using namespace std;
typedef long long LL;

const int N = 2010;
int dp[N][N];
int w[N], v[N];

int main() {
    int n, maxw;
    cin >> n >> maxw;
    for (int i = 0;i < n;i++) {
        cin >> w[i] >> v[i];
    }

    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= maxw;j++) {
            dp[i][j] = dp[i - 1][j];
            if (j >= w[i - 1])
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i - 1]] + v[i - 1]);
        }
    }
    cout << dp[n][maxw];

    return 0;
}

01背包（回溯）

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
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;



#define MAX 2000
int maxv;
int maxw;
int x[MAX];
int W;
int n;
int w[MAX];
int v[MAX];

void knap(int i, int tw, int tv, int op[])
{
    int j;
    if (i >= n)
    {
        if (tw <= W && tv > maxv)
        {
            maxv = tv;
            maxw = tw;
            for (j = 1;j < n;j++)
                x[j] = op[j];
        }
    }
    else
    {
        op[i] = 1;
        knap(i + 1, tw + w[i], tv + v[i], op);
        op[i] = 0;
        knap(i + 1, tw, tv, op);
    }
}

int main(void)
{
    cin >> n >> W;
    int op[MAX];		//临时解
    for (int i = 0;i < n;i++) {
        cin >> w[i] >> v[i];
    }
    knap(0, 0, 0, op);
    cout << maxv;

    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
#include<algorithm>
#include<iostream>

using namespace std;
const int N = 1e4;
int v[N], w[N];
int dp[N];

int main() {
    int n, maxw;
    cin >> n >> maxw;

    for (int i = 0;i < n;i++)cin >> w[i] >> v[i];

    for (int i = 0;i < n;i++) {
        for (int j = w[i];j <= maxw;j++) {
            if (j >= w[i])
                dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }

    cout << dp[maxw];
    return 0;
}

多重背包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
// 多重背包1
// 直接拆成01背包
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 1010;
int dp[N];

int main() {
    int n, maxv;
    cin >> n >> maxv;

    for (int i = 0;i < n;i++) {
        int v, w, s;
        cin >> w >> v >> s;
        while(s--) {
            for (int j = maxv;j >= w;j--)
                dp[j] = max(dp[j], dp[j - w] + v);
        }
    }
    cout<<dp[maxv]<<endl;


    return 0;
}

多重背包2

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
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 100010;
int dp[N], weight[N], value[N];
int cnt;


int main() {
    int n, maxw;
    cin >> n >> maxw;
    for (int i = 0;i < n;i++) {
        int w, v, s;
        cin >> w >> v >> s;
        int j = 1;
        while (s) {
            if (s < j) j = s;
            weight[cnt] = w * j;
            value[cnt] = v * j;
            cnt++;
            s -= j;
            j *= 2;
        }
    }

    for (int i = 0; i < cnt; i++) {
        for (int j = maxw;j >= weight[i];j--) {
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

    cout<<dp[maxw]<<endl;


    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
27
28
29
30
31
32
33
34
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 1100;
int  s[N], w[N][N], v[N][N], dp[N*N];


int main() {
    int n, maxw;
    cin >> n >> maxw;

    for (int i = 0;i < n;i++) {
        cin >> s[i];
        for (int j = 0;j < s[i];j++) {
            cin >> w[i][j] >> v[i][j];
        }
    }

    for (int i = 0;i < n;i++) {
        for (int k = maxw;k >= 0;k--) {
            for (int j = 0;j < s[i];j++) {
                if(k>=w[i][j])
                    dp[k] = max(dp[k], dp[k - w[i][j]] + v[i][j]);
            }
        }
    }

    cout << dp[maxw];

    return 0;
}

线性DP

数字三角形

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 <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;

const int N = 610;
int num[N][N];
int main() {
    int n;
    cin >> n;
    memset(num, 0xcf, sizeof(num));

    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= i;j++) {
            cin >> num[i][j];
        }
    }


    for (int i = 2;i <= n;i++) {
        for (int j = 1;j <= i;j++) {
            num[i][j] += max(num[i - 1][j - 1], num[i - 1][j]);
        }
    }

    int maxn = -1e8;
    for (int i = 1;i <= n;i++)
        maxn = max(maxn, num[n][i]);

    cout << maxn << endl;

    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
27
28
29
30
31
32
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 10010;
int num[N], ans[N];

int main() {
    int n;
    cin >> n;

    for (int i = 1;i <= n;i++) cin >> num[i];

    for (int i = 2;i <= n;i++) {
        for (int j = 1;j < i;j++) {
            if (num[i] > num[j]) {
                ans[i] = max(ans[i], ans[j] + 1);
            }
        }
    }

    int res = 0;
    for (int i = 1;i <= n;i++)
        res = max(res, ans[i]);


    cout << res + 1 << endl;

    return 0;
}

最长上升子序列2

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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;

const int N = 100010;
int num[N];


int main() {
    int n;
    cin >> n;

    for (int i = 1;i <= n;i++) cin >> num[i];

    // 题解中最难理解的地方在于栈中序列虽然递增，但是每个元素在原串中对应的位置其实可能是乱的，
    // 那为什么这个栈还能用于计算最长子序列长度？
    // 实际上这个栈【不用于记录最终的最长子序列】，而是【以stk[i]结尾的子串长度最长为i】
    // 或者说【长度为i的递增子串中，末尾元素最小的是stk[i]】。理解了这个问题以后就知道为什么新进来的元素要不就在末尾增加，要不就替代第一个大于等于它元素的位置。
    // 这里的【替换】就蕴含了一个贪心的思想，对于同样长度的子串，我当然希望它的末端越小越好，这样以后我也有更多机会拓展。

    // ans记录的并不是最长上升子序列，只是记录了长度
    vector<int> ans;
    ans.push_back(num[1]);
    for (int i = 2;i <= n;i++) {
        if (num[i] > ans.back())
            ans.push_back(num[i]);
        else 
            // lower_bound：查找第一个大于等于num[i]的元素
            *lower_bound(ans.begin(), ans.end(), num[i]) = num[i];
    }

    cout << ans.size() << endl;

    return 0;
}

最长公共子序列（LCS）

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 <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int MAX = 1100;
int ans[MAX][MAX];


int main() {
    int n, m;
    cin >> n >> m;
    char N[MAX], M[MAX];
    cin >> N + 1 >> M + 1;

    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (N[i] == M[j]) ans[i][j] = ans[i - 1][j - 1] + 1;
            else ans[i][j] = max(ans[i - 1][j], ans[i][j - 1]);
        }
    }

    cout << ans[n][m] << endl;


    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
27
28
29
30
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 1010;
int dp[N][N];


int main() {
    int n, m;
    char a[N], b[N];
    cin >> n >> a + 1 >> m >> b + 1;

    // 注意初始化
    for (int i = 1; i <= n; i++) dp[i][0] = i;
    for (int i = 1; i <= m; i++) dp[0][i] = i;
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] }) + 1;
        }
    }

    cout << dp[n][m] << endl;


    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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;

const int N = 1010;
int dp[N][N];
char str[N][N];

int check(char a[], int n, char b[], int m) {
    // memset还是很慢的，尤其是要做2e4的情况下
    // memset(dp, 0, sizeof(dp));
    for (int i = 0; i <= n + 2; i++) dp[i][0] = i;
    for (int i = 0; i <= m + 2;i++) dp[0][i] = i;

    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = min({ dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1] }) + 1;
        }
    }
    return dp[n][m];
}

int main() {
    int n, m;
    cin >> n >> m;

    for (int i = 1;i <= n;i++) scanf("%s", str[i] + 1);

    for (int i = 0;i < m;i++) {
        int ans = 0, target;
        char a[N];
        scanf("%s", a + 1);
        cin >> target;

        for (int j = 1;j <= n;j++) {
            if (check(str[j], strlen(str[j] + 1), a, strlen(a + 1)) <= target) ans++;;
        }
        cout << ans << endl;
    }

    

    return 0;
}

区间DP

石子合并

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
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 1010;
int f[N][N];
// f[i][j]记录合并i到j的最小代价

int main() {
    int n;
    cin >> n;
    int s[N] = { 0 };
    for (int i = 1;i <= n;i++) {
        cin >> s[i];
        s[i] += s[i - 1];
    }

    for (int len = 2;len <= n;len++) {
        for (int i = 1;i + len - 1 <= n;i++) {
            int j = i + len - 1;
            f[i][j] = 1e8;
            for (int k = i;k < j;k++) {
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
            }
        }
    }
    cout << f[1][n];


    return 0;
}

计数DP

整数划分

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
// 和完全背包类似
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 100010;
const int mod = 1e9 + 7;
int n, dp[N];

int main() {
    cin >> n;
    dp[0] = 1;

    for (int i = 1;i <= n;i++) {
        for (int j = i;j <= n;j++) {
            dp[j] = (dp[j] + dp[j - i]) % mod;
        }
    }

    cout << dp[n] << endl;

    return 0;
}

数位DP

计数问题

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
#include <bits/stdc++.h>
using namespace std;
const int N = 15;
typedef long long ll;
ll l = 0, r = 0, dp[N] = { 0 }, mi[N] = { 0 };
ll ans1[N] = { 0 }, ans2[N] = { 0 };
int a[N] = { 0 };

void solve(ll n, ll* ans) {
    int len = 0;
    ll tmp = n;
    while (n) a[++len] = n % 10, n /= 10;
    // 分解 n 的每个位上的数字，保存在数组 a 中，len 表示数字的位数

    for (int i = len; i >= 1; --i) {
        for (int j = 0; j < 10; j++) ans[j] += dp[i - 1] * a[i];
        // 对于当前位的数字 a[i]，它对于所有数字的出现次数贡献是 dp[i - 1] * a[i]

        for (int j = 0; j < a[i]; j++) ans[j] += mi[i - 1];
        // 对于当前位之前的数字，它们的各位上的数字都能与 a[i] 组成更小的数字，贡献是 mi[i - 1]

        tmp -= mi[i - 1] * a[i], ans[a[i]] += tmp + 1;
        // 对于当前位的数字 a[i]，其在当前位的出现次数是 tmp + 1，其中 tmp 表示除了当前位之外的数字组成的数

        ans[0] -= mi[i - 1];
        // 数字 0 出现在当前位的次数是当前位之前的数字组成的数 mi[i - 1]
    }
}


int main() {
    mi[0] = 1ll;

    // 设数组 dp[i] 为满 i 位的数中每个数字出现的次数，此时暂时不处理前导零
    for (int i = 1; i <= 13; ++i) {
        dp[i] = dp[i - 1] * 10 + mi[i - 1];
        mi[i] = 10ll * mi[i - 1];
    }
    while (1) {
        scanf("%lld%lld", &l, &r);
        if (l > r) swap(l, r);
        if (l == 0 && r == 0) break;
        memset(ans1, 0, sizeof(ans1));
        memset(ans2, 0, sizeof(ans2));
        memset(a, 0, sizeof(a));
        solve(r, ans1), solve(l - 1, ans2);
        // cout<<l<<" "<<r<<endl;
        for (int i = 0; i < 10; ++i) printf("%lld ", ans1[i] - ans2[i]);
        cout << "\n";
    }
    return 0;
}


状压DP（插头DP）

蒙德里安的梦想_yxc

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/*
下文对  if ((j & k ) == 0 && st[ j | k] )  有清晰的解释！！！
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 12, M = 1 << N;
long long f[N][M];// 第一维表示列， 第二维表示所有可能的状态
bool st[M];  //存储每种状态是否有奇数个连续的0，如果奇数个0是无效状态，如果是偶数个零置为true。
//vector<int > state[M];  //二维数组记录合法的状态
vector<vector<int>> state(M);  //两种写法等价:二维数组，M是行大小
int m, n;

int main() {

    while (cin >> n >> m, n || m) { //读入n和m，并且不是两个0即合法输入就继续读入

        //第一部分：预处理1
        //对于每种状态，先预处理每列不能有奇数个连续的0

        for (int i = 0; i < (1 << n); i++) {

            int cnt = 0;//记录连续的0的个数

            bool isValid = true; // 某种状态没有奇数个连续的0则标记为true

            for (int j = 0; j < n; j++) { //遍历这一列，从上到下

                if ((i >> j) & 1) {
                    //i >> j位运算，表示i（i在此处是一种状态）的二进制数的第j位； 
                    // &1为判断该位是否为1，如果为1进入if
                    if (cnt & 1) {
                        //这一位为1，看前面连续的0的个数，如果是奇数（cnt &1为真）则该状态不合法
                        isValid = false; break;
                    }

                    cnt = 0; // 既然该位是1，并且前面不是奇数个0（经过上面的if判断），计数器清零。
                    //其实清不清零没有影响
                }
                else cnt++; //否则的话该位还是0，则统计连续0的计数器++。
            }
            if (cnt & 1)  isValid = false; //最下面的那一段判断一下连续的0的个数

            st[i] = isValid; //状态i是否有奇数个连续的0的情况,输入到数组st中
        }

        // 第二部分：预处理2
        // 经过上面每种状态 连续0的判断，已经筛掉一些状态。
        // 下面来看进一步的判断：看第i-2列伸出来的和第i-1列伸出去的是否冲突

        for (int j = 0; j < (1 << n); j++) { //对于第i列的所有状态
            state[j].clear(); //清空上次操作遗留的状态，防止影响本次状态。

            for (int k = 0; k < (1 << n); k++) { //对于第i-1列所有状态
                if ((j & k) == 0 && st[j | k])
                    // 第i-2列伸出来的 和第i-1列伸出来的不冲突(不在同一行) 
                    // 解释一下st[j | k] 
                    // 已经知道st[]数组表示的是这一列没有连续奇数个0的情况，
                    // 我们要考虑的是第i-1列（第i-1列是这里的主体）中从第i-2列横插过来的，
                    // 还要考虑自己这一列（i-1列）横插到第i列的
                    // 比如 第i-2列插过来的是k=10101，第i-1列插出去到第i列的是 j =01000，
                    // 那么合在第i-1列，到底有多少个1呢？
                    // 自然想到的就是这两个操作共同的结果：两个状态或。 j | k = 01000 | 10101 = 11101
                    // 这个 j|k 就是当前 第i-1列的到底有几个1，即哪几行是横着放格子的
                    state[j].push_back(k);
                //二维数组state[j]表示第j行， 
                //j表示 第i列“真正”可行的状态，
                //如果第i-1列的状态k和j不冲突则压入state数组中的第j行。
                //“真正”可行是指：既没有前后两列伸进伸出的冲突；又没有连续奇数个0。
            }

        }

        //第三部分：dp开始

        memset(f, 0, sizeof f);
        //全部初始化为0，因为是连续读入，这里是一个清空操作。
        //类似上面的state[j].clear()

        f[0][0] = 1;// 这里需要回忆状态表示的定义
        //按定义这里是：前第-1列都摆好，且从-1列到第0列伸出来的状态为0的方案数。
        //首先，这里没有-1列，最少也是0列。
        //其次，没有伸出来，即没有横着摆的。即这里第0列只有竖着摆这1种状态。

        for (int i = 1; i <= m; i++) { //遍历每一列:第i列合法范围是(0~m-1列)
            for (int j = 0; j < (1 << n); j++) {  //遍历当前列（第i列）所有状态j
                for (auto k : state[j])    // 遍历第i-1列的状态k，如果“真正”可行，就转移
                    f[i][j] += f[i - 1][k];    // 当前列的方案数就等于之前的第i-1列所有状态k的累加。
            }
        }

        //最后答案是什么呢？
        //f[m][0]表示 前m-1列都处理完，并且第m-1列没有伸出来的所有方案数。
        //即整个棋盘处理完的方案数

        cout << f[m][0] << endl;

    }
}


// 作者：ShizhengLee
// 链接：https ://www.acwing.com/solution/content/28088/
// 来源：AcWing
// 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

蒙德里安的梦想_OI wiki

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
// 蒙德里安的梦想
// 不会写
// 插头DP：https://oi-wiki.org/dp/plug/

#include <bits/stdc++.h>
using namespace std;
const int N = 11;
long long f[2][1 << N], * f0, * f1;
int n, m;

int main() {
    while (cin >> n >> m && n) {
        f0 = f[0];
        f1 = f[1];
        fill(f1, f1 + (1 << m), 0);
        f1[0] = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                swap(f0, f1);
                fill(f1, f1 + (1 << m), 0);
                #define u f0[s]
                for (int s = 0; s < 1 << m; ++s)
                    if (u) {
                        if (j != m - 1 && (!(s >> j & 3))) f1[s ^ 1 << j + 1] += u;  // 横放
                        f1[s ^ 1 << j] += u;  // 竖放或不放
                    }
            }
        }
        cout << f1[0] << endl;
    }
}


最短哈密顿路径

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
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;

const int N = 21;
int weight[N][N];
int dp[1 << N][N];

int main() {
    int n;
    cin >> n;

    for (int i = 0;i < n;i++)
        for (int j = 0;j < n;j++)
            cin >> weight[i][j];

    memset(dp, 0x3f, sizeof(dp));
    dp[1][0] = 0;
    // 枚举哪些点被用过
    // 目前停在哪个点上
    for (int i = 0;i < 1 << n;i++) // 枚举所有可能的走法
        for (int j = 0;j < n;j++) // 枚举所有的点
            if (i >> j & 1)     // 只枚举在目前走法中的点
                for (int k = 0;k < n;k++) // 这句和下句：枚举这个走法中所有的点
                    if (i >> k & 1)
                        // 松弛（Floyd）
                        // dp[i - (1 << j)][k]就是上一状态，之前已经求出来了
                        dp[i][j] = min(dp[i][j], dp[i - (1 << j)][k] + weight[k][j]);

    cout << dp[(1 << n) - 1][n - 1];

    return 0;
}

没有上司的舞会（树形DP）

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
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;

const int N = 100010;
int e[N], ne[N], h[N], idx;
int dp[N][10], has_father[N];
bool vis[N];


void insert(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void calc(int k) {
    vis[k] = true;
    for (int i = h[k];~i;i = ne[i]) {
        int v = e[i];
        if (!vis[v]) {
            calc(v);
            dp[k][0] += max(dp[v][0], dp[v][1]);
            dp[k][1] += dp[v][0];
        }
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> dp[i][1];
    }

    memset(h, -1, sizeof(h));
    for (int i = 0;i < n - 1;i++) {
        int a, b;
        cin >> a >> b;
        insert(b, a);
        has_father[a] = 1;
    }

    for (int i = 1;i <= n;i++) {
        if (!has_father[i]) {
            calc(i);
            cout << max(dp[i][0], dp[i][1]) << endl;
            return 0;
        }
    }

    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
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
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;

const int N = 1010;
int n, m;
int map[N][N], dp[N][N];
bool vis[N][N];
int d[4][2] = { {0,-1},{0,1},{1,0},{-1,0} };

bool legal(int xx, int yy) {
    return xx >= 0 && xx < n && yy >= 0 && yy < m;
}

int bfs(int a, int b) {
    vis[a][b] = true;
    if (!dp[a][b])
        dp[a][b] = 1;
    else
        return dp[a][b];
    for (int i = 0;i < 4;i++) {
        int xx = a + d[i][0], yy = b + d[i][1];
        if (map[a][b] <= map[xx][yy] || !legal(xx, yy)) continue;
        dp[a][b] = max(dp[a][b], bfs(xx, yy) + 1);
    }
    return dp[a][b];
}

int main() {
    cin >> n >> m;
    for (int i = 0;i < n;i++)
        for (int j = 0;j < m;j++)
            cin >> map[i][j];

    int ans = 0;
    // fill(dp, dp + N * N, 1);
    for (int i = 0;i < n;i++)
        for (int j = 0;j < m;j++)
            ans = max(ans, bfs(i, j));
    for (int i = 0;i < n;i++) {
        for (int j = 0;j < m;j++)
            cout << dp[i][j] << " ";
        cout << endl;
    }

    cout << ans;

    return 0;
}

#AcWing #算法题 #动态规划
AcWing 第5讲 动态规划
https://asxjdb.github.io/2023/08/15/AcWing-ch5/
作者
Asxjdb
发布于
2023年8月15日
许可协议