很楠不爱3

这个屌丝很懒，什么也没留下！

热门标签

NENUOJ 算法2 动态规划D

作者：很楠不爱3 | 2024-06-15 06:05:33

踩

nenuoj

剩余oj例题的代码思路已更新到本人网站上，指路：DODOLA’s

算法2动态规划D

1272: D001 数字三角形

题目描述

7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

上图给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，你的任务就是找到最大的和。

注意：路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。

输入

输入的第一行是一个整数N (1 < N <= 100)，给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。

输出

输出最大的和。

样例输入

样例输出

30
1

注意：这题在nenuOJ里是多组输入（虽然它题干没写）

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 120;
ll number[maxn][maxn];
ll dp[maxn][maxn]; // 记录走到(i,j)点时最好的和

int main() {
    int n;
    while (cin >> n) {
        for (int i = 1;i <= n;i++)
            for (int j = 1;j <= i;j++)
                cin >> number[i][j];
        for (int i = 1;i < n;i++)
            dp[n][i] = number[n][i];
        for (int i = n;i > 1;i--) {
            for (int j = 1;j <= i;j++) {
                dp[i - 1][j] = max(dp[i][j], dp[i][j + 1]) + number[i - 1][j];
            }
        }
        cout << dp[1][1] << 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

1273: D002 最长上升子序列

题目描述

一个数的序列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)等等。这些子序列中最长的长度是4，比如子序列(1, 3, 5, 8)。

你的任务，就是对于给定的序列，求出最长上升子序列的长度。

输入

输入有很多组，每组输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到10000。

输出

输出每组的最长上升子序列的长度。

样例输入

7
1 7 3 5 9 4 8
6
2 3 4 1 6 5
1
2
3
4

样例输出

AC代码

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 1010;
int a[maxn];
// int dp[maxn];
int main() {
    int n;
    while (cin >> n) {
        for (int i = 1;i <= n;i++)cin >> a[i];
        vector<int> lmax;
        lmax.push_back(a[1]);
        for (int i = 2;i <= n;i++) {
            if (a[i] > lmax.back()) {
                lmax.push_back(a[i]);
            }
            else if (a[i] < lmax.back()) {
                int l = 0, r = lmax.size() - 1;
                
                while (l < r) {
                    int md = (l + r) / 2;
                    if (lmax[md] <= a[i])l = md + 1;
                    else r = md;
                }
                lmax[l] = a[i];
            }
            // for (int j = 0;j < lmax.size();j++)
            //     cout << lmax[j] << " ";
            // cout << endl;
        }
        cout << lmax.size() << 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

1274: D003 Help Jimmy

题目描述

“Help Jimmy” 是在下图所示的场景上完成的游戏：

场景中包括多个长度和高度各不相同的平台。地面是最低的平台，高度为零，长度无限。
Jimmy老鼠在时刻0从高于所有平台的某处开始下落，它的下落速度始终为1米/秒。当Jimmy落到某个平台上时，游戏者选择让它向左还是向右跑，它跑动的速度也是1米/秒。当Jimmy跑到平台的边缘时，开始继续下落。Jimmy每次下落的高度不能超过MAX米，不然就会摔死，游戏也会结束。
设计一个程序，计算Jimmy到地面时可能的最早时间。

输入

第一行是测试数据的组数t（0 <= t <= 20）。每组测试数据的第一行是四个整数N，X，Y，MAX，用空格分隔。N是平台的数目（不包括地面），X和Y是Jimmy开始下落的位置的横竖坐标，MAX是一次下落的最大高度。接下来的N行每行描述一个平台，包括三个整数，X1[i]，X2[i]和H[i]。H[i]表示平台的高度，X1[i]和X2[i]表示平台左右端点的横坐标。1<= N <= 1000，-20000 <= X, X1[i], X2[i] <= 20000，0 < H[i] < Y <= 20000（i = 1…N）。所有坐标的单位都是米。
Jimmy 的大小和平台的厚度均忽略不计。如果Jimmy 恰好落在某个平台的边缘，被视为落在平台上。所有的平台均不重叠或相连。测试数据保Jimmy一定能安全到达地面。

输出

对输入的每组测试数据，输出一个整数，Jimmy到地面时可能的最早时间。

样例输入

样例输出

23
1

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e4 + 20;
struct PT {
    int x1, x2, h;
    bool operator<(const PT& P)const {
        return h > P.h;
    }
}pt[maxn];
int n, x, y, mx;
int findnext(int id, int x) {
    // 寻找x下的第一块板
    for (int i = id + 1;i <= n + 1;i++) {
        if (pt[i].x1 <= x && pt[i].x2 >= x) {
            return i;
        }
    }
    return -1;
}
int fun[maxn];
int dfs(int id, int p, int from) {
    // cout << id << " " << p << " " << from << endl;
    int lp = pt[id].x1, rp = pt[id].x2;
    // 当前是否到达终点
    if (id == n + 1)
        return 0;
    int lenl = -1, lenr = -1;
    // 左走
    int lpid = findnext(id, lp);
    if (lpid != -1 && pt[id].h - pt[lpid].h <= mx) {
        // 可走
        lenl= dfs(lpid, lp, id);
    }
    // 右走
    int rpid = findnext(id, rp);
    if (rpid != -1 && pt[id].h - pt[rpid].h <= mx) {
        // 可走
        lenr= dfs(rpid, rp, id);
    }
    if (lenl != -1 && lenr != -1)
        return fun[id] = min(lenl + p - lp, lenr + rp - p);
    else if (lenl == -1)
        return fun[id] = lenr + rp - p;
    else if (lenr == -1)
        return fun[id] = lenl + p - lp;
    else
        return 0;
}

int main() {
    int t;cin >> t;
    while (t--) {
        cin >> n >> x >> y >> mx;
        pt[0].x1 = x;pt[0].x2 = x;pt[0].h = y;
        for (int i = 1;i <= n;i++) {
            cin >> pt[i].x1 >> pt[i].x2 >> pt[i].h;
        }
        pt[n + 1].h = 0;pt[n + 1].x1 = -maxn;pt[n + 1].x2 = maxn;
        sort(pt, pt + n + 1);
        // 从高到低排列
        dfs(0, x, -1);
        cout << y + fun[0] << 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

1275: D004 最长公共子序列

题目描述

我们称序列Z = < z1, z2, …, zk >是序列X = < x1, x2, …, xm >的子序列当且仅当存在严格上升的序列< i1, i2, …, ik >，使得对j = 1, 2, … ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b,c, f, b, c >的子序列。
现在给出两个序列X和Y，你的任务是找到X和Y的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z既是X的子序列也是Y的子序列。

输入

输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200的字符串，表示两个序列。两个字符串之间由若干个空格隔开。

输出

输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200的字符串，表示两个序列。两个字符串之间由若干个空格隔开。

样例输入

abcfbc abfcab
programming contest
abcd mnp
1
2
3

样例输出

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 220;
int dp[maxn][maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s, t;
    while (cin >> s >> t) {
        s = " " + s;t = " " + t;
        memset(dp, 0, sizeof(dp));
        for (int i = 1;i < s.size();i++) {
            for (int j = 1;j < t.size();j++) {
                if (s[i] == t[j])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        cout << dp[s.size() - 1][t.size() - 1] << 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

1276: D005 陪审团的人选

题目描述

在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n个人作为陪审团的候选人，然后再从这n个人中选m人组成陪审团。选m人的办法是：
控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0到20。为了公平起见，法官选出陪审团的原则是：选出的m个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。最终选出的方案称为陪审团方案。

输入

输入包含多组数据。每组数据的第一行是两个整数n和m，n是候选人数目，m是陪审团人数。注意，1<=n<=200, 1<=m<=20而且m<=n。接下来的n行，每行表示一个候选人的信息，它包含2个整数，先后是控方和辩方对该候选人的打分。候选人按出现的先后从1开始编号。两组有效数据之间以空行分隔。最后一组数据n=m=0。

输出

对每组数据，先输出一行，表示答案所属的组号, 如 ‘Jury #1’, ‘Jury #2’, 等。接下来的一行要象例子那样输出陪审团的控方总分和辩方总分。再下来一行要以升序输出陪审团里每个成员的编号，两个成员编号之间用空格分隔。每组输出数据须以一个空行结束。

样例输入

样例输出

Jury #1
Best jury has value 6 for prosecution and value 4 for defence:
2 3
1
2
3

AC代码

#include<bits/stdc++.h>
using namespace std;

const int N = 205;
const int inf = 0x3f;
int dp[N][25][4 * N], a[N], b[N];
vector<int> mark;

int main()
{
    int n, m, T = 1;
    while (cin >> n >> m && n) {
        mark.clear();
        memset(dp, -inf, sizeof(dp));
        dp[0][0][400] = 0;
        for (int i = 1;i <= n;i++) {
            cin >> a[i] >> b[i];
        }
        for (int i = 1;i <= n;i++) {
            for (int j = 0;j <= m;j++) {
                for (int k = 0;k <= 800;k++) {
                    dp[i][j][k] = dp[i - 1][j][k];
                    int tt = k - a[i] + b[i];
                    if (tt < 0 || tt >= 800)
                        continue;
                    if (j == 0)
                        continue;
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][tt] + a[i] + b[i]);
                }
            }
        }
        int t = 0;
        while (dp[n][m][t + 400] < 0 && dp[n][m][-t + 400] < 0) t++;
        if (dp[n][m][t + 400] > dp[n][m][-t + 400]) t += 400;
        else t = 400 - t;

        int nn = n, mm = m, cnt = 0;
        while (mm) {
            if (dp[nn][mm][t] == dp[nn - 1][mm][t]) {
                nn--;
            }
            else {
                mark.push_back(nn);
                t -= a[nn] - b[nn];
                nn--;mm--;
                cnt++;
            }
        }
        int sum1 = 0, sum2 = 0;
        for (int i = 0;i < cnt;i++) {
            sum1 += a[mark[i]];
            sum2 += b[mark[i]];
        }
        cout << "Jury #" << T++ << "\nBest jury has value " << sum1 << " for prosecution and value " << sum2 << " for defence:\n";
        for (int i = cnt - 1;i >= 0;i--)
            cout << mark[i] << ' ';
        cout << "\n\n";
    }

    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
52
53
54
55
56
57
58
59
60
61

1277: D006 最大和

题目描述

给定一个n个整数的集合：A={a1, a2,…, an}，我们如下定义函数d(A)：
$d(A)=\max\limits_{1\leq s_1\leq t_1\leq s_2\leq t_2\leq n}$

{\begin{matrix} \sum_{i = s_{1}}^{t_{1}} a_{i} + \sum_{j = s_{2}}^{t_{2}} a_{j} \end{matrix}}

$\begin{Bmatrix} \sum_{i=s_1}^{t_1}a_i+\sum_{j=s_2}^{t_2}a_j\\ \end{Bmatrix}$

d (A) = 1 \leq s_{1} \leq t_{1} \leq s_{2} \leq t_{2} \leq n max {\sum_{i = s_{1}}^{t_{1}} a_{i} + \sum_{j = s_{2}}^{t_{2}} a_{j}}

你的任务就是计算函数d(A)的函数值。
提示：对于样例，我们选择{2,2,3,-3,4} 和 {5}，进行想加得到函数d(A)的函数值。
输入量大，建议使用scanf();

输入

输入包含 T(<=30)个样例，在输入的第一行即是整数T。每个样例包含两行，第一行是整数 n(2<=n<=50000)，第二行包含了n个整数： a1, a2, …, an. (|ai| <= 10000)。

输出

对于每个输入样例，输出一行，即如上定义函数d(A)的函数值。

样例输入

1
10
1 -1 2 2 3 -3 4 -4 5 -5
1
2
3

样例输出

13
1

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2200;
int a[maxn];
int leftt[maxn], rightt[maxn];
int lmax[maxn], rmax[maxn];
int main() {
    int t;cin >> t;
    while (t--) {
        int n;cin >> n;
        for (int i = 1;i <= n;i++)
            cin >> a[i];
        leftt[1] = a[1];rightt[n] = a[n];
        lmax[1] = a[1];rmax[n] = a[n];
        for (int i = 2;i <= n;i++) {
            leftt[i] = max(leftt[i - 1] + a[i], a[i]);
            lmax[i] = max(lmax[i - 1], leftt[i]);
        }
        for (int i = n - 1;i > 0;i--){
            rightt[i] = max(rightt[i + 1] + a[i], a[i]);
            rmax[i] = max(rmax[i + 1], rightt[i]);
        }
        int ans = a[1];
        for (int i = 2;i <= n;i++)
            ans = max(ans, lmax[i - 1] + rmax[i]);
        cout << ans << 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

1278: D007 最大子矩阵

题目描述

给你一个二维矩阵，元素是整数，有正有负。一个子矩阵就是最小1*1最大包含这个矩阵本身的矩阵。一个矩阵的和就是矩阵中所有元素求和，最大子矩阵就是所有子矩阵中和最大的那个字矩阵。下面是一个例子：
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
最大子矩阵在左下角
9 2
-4 1
-1 8
和值是15。

输入

输入的第一行是整数N，即表示要输入一个N * N的整数矩阵。接下来是N^2 个整数，每个整数之间被空格或者空行分开，这些整数即为矩阵中的数，按照列优先的顺序排列，即第一行整数从左至右输入，第二行从左至右输入…. 第n行从左至右输入。N不会大于100，矩阵中的整数范围为 [-127,127]。

输出

输出最大矩阵的和。

样例输入

4
0 -2 -7 0 9 2 -6 2
-4 1 -4  1 -1 8  0 -2
1
2
3

样例输出

15
1

二维前缀和+穷举QwQ

AC代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 120;
int rec[maxn][maxn];
int pre[maxn][maxn];
int dp[maxn][maxn];
int main() {
    int n;cin >> n;
    pre[0][0] = 0;
    // 二维前缀和
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= n;j++) {
            cin >> rec[i][j];
            pre[i][j] = pre[i - 1][j] + pre[i][j - 1] - pre[i - 1][j - 1] + rec[i][j];
        }
    }
    // for (int i = 1;i <= n;i++) {
    //     for (int j = 1;j <= n;j++) {
    //         cout << pre[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    int ans = -200;
    for (int xi = 1;xi <= n;xi++) {
        for (int yi = 1;yi <= n;yi++) {
            for (int xj = xi;xj <= n;xj++) {
                for (int yj = yi;yj <= n;yj++) {
                    int sum = pre[xj][yj] - pre[xi - 1][yj] - pre[xj][yi - 1] + pre[xi - 1][yi - 1];
                    ans = max(ans, sum);
                }
            }
        }
    }
    cout << ans << 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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/很楠不爱3/article/detail/721178

NENUOJ 算法2 动态规划D

算法2动态规划D

文章目录

1272: D001 数字三角形

题目描述

AC代码

1273: D002 最长上升子序列

题目描述

AC代码

1274: D003 Help Jimmy

题目描述

AC代码

1275: D004 最长公共子序列

题目描述

AC代码

1276: D005 陪审团的人选

题目描述

AC代码

1277: D006 最大和

题目描述

AC代码

1278: D007 最大子矩阵

题目描述

AC代码