2020 年动态规划专题训练赛 01

集训 DP 专场 01 (9/10).

A. HDU 2041 超级楼梯

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

using namespace std;

const int N = 50;

long long f[N];

void init() {
    f[1] = 1, f[2] = 1, f[3] = 2;
    for (int i = 4; i < N; i++) {
        f[i] = f[i - 1] + f[i - 2];
    }
}

int main() {
    init();
    int n; cin >> n;
    while (n--) {
        int x; scanf("%d", &x);
        printf("%lld\n", f[x]);
    }
    return 0;
}

B. POJ 1163 The Triangle

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

using namespace std;

const int N = 1010;

int n;
int w[N][N];
int f[N][N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++)
            cin >> w[i][j];
    }
    for (int i = n; i; i--) {
        for (int j = i; j; j--)
            f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + w[i][j];
    }
    cout << f[1][1] << endl;
    return 0;
}

C. POJ2419 Maximum Sum

做法：求两段不相交区间和的最大值。正反dp一遍求出 $i$ 和 $i$ 左侧的连续区间的最大和，$i$ 和 $i$ 右侧连续区间的最大和，然后枚举分界点即可。

 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 <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 50010;

int n, T;
LL a[N];
LL f[N], g[N];

void solve() {
    scanf("%d", &n);
    memset(f, -0x3f, sizeof f);
    memset(g, -0x3f, sizeof g);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++) f[i] = max(a[i], f[i - 1] + a[i]);
    for (int i = n; i >= 1; i--) g[i] = max(a[i], g[i + 1] + a[i]);
    for (int i = 1; i <= n; i++) f[i] = max(f[i], f[i - 1]);
    for (int i = n; i >= 1; i--) g[i] = max(g[i], g[i + 1]);
    LL res = -1e18;
    for (int i = 1; i <= n - 1; i++) res = max(res, f[i] + g[i + 1]);
    cout << res << endl;
}

int main() {
    cin >> T;
    while (T--) solve();
    return 0;
}

D. CodeForces 846A Curriculum Vitae

做法：最后的序列一定是 0000111 形式的，求非严格 LIS 即可。

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

using namespace std;

const int N = 110;

int n;
int a[N], f[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        f[i] = 1;
        for (int j = 1; j < i; j++) {
            if (a[j] <= a[i])
                f[i] = max(f[i], f[j] + 1);
        }
    }
    int res = 0;
    for (int i = 1; i <= n; i++) res = max(res, f[i]);
    cout << res << endl;
    return 0;
}

E. CodeForces 650D Zip-line（完全不会）

F. CodeForces 10D LCIS

去年做过的一个题：https://ketchuppp.xyz/post/Codeforces10D-LCIS/

G. CodeForces 1038D Slime（已补）

开始还想怎么区间dp，一看数据范围就不太行。
做法：贪心、思维题。最优的情况一定是，只有相邻两项取了差值的绝对值，其他项都可以取到自身的绝对值。所以只要暴力循环一遍，$i$ 和 $i+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
29
30
31
32
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

typedef long long LL;

const int N = 500010;

int n;
LL a[N], b[N];

int main() {
    cin >> n;
    LL sum = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        b[i] = abs(a[i]);
        sum += b[i];
    }
    LL res = 0;
    for (int i = 1; i <= n - 1; i++) {
        // i, i+1
        res = max(res, sum - (b[i] + b[i + 1]) + abs(a[i] - a[i + 1]));
    }
    if (n == 1) cout << a[1] << endl;
    else cout << res << endl;
    return 0;
}

H. UVA 11584 Partitioning by Palindromes

$f[i]$ 表示将前 $i$ 个分割成回文串的最小个数，暴力枚举一下 $j$，$[j,i]$ 区间是回文就可以转移。

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

using namespace std;

typedef long long LL;

const int N = 1010;

int n, T;
int f[N]; // f[i]表示将前i个分割成回文串的最小个数
char s[N];

bool check(int l, int r) {
    int i = l, j = r;
    bool flag = true;
    while (i < j) {
        if (s[i] != s[j]) {
            flag = false;
            break;
        }
        i++, j--;
    }
    return flag;
}

void solve() {
    scanf("%s", s + 1);
    n = strlen(s + 1);
    memset(f, 0x3f, sizeof f);
    f[0] = 0;
    for (int i = 1; i <= n; i++) {
        f[i] = f[i - 1] + 1;
        for (int j = 1; j < i; j++) {
            if (check(j, i)) {
                f[i] = min(f[i], f[j - 1] + 1);
            }
        }
    }
    // cout << check(3, 5) << endl;
    // cout << f[5] << endl;
    cout << f[n] << endl;
}

int main() {
    cin >> T;
    while (T--) solve();
    return 0;
}

I. CodeForces 1133E K Balanced Teams（已补）

题意：给定 $n$ 个数，分成 $k$ 组，要求组内最大值和最小值的差值不超过 $5$，问 $k$ 组最多能包含几个数。

做法：$f[i][j]$ 表示前 $i$ 个人中分了 $j$ 组的最大人数。以第 $i$ 个人在不组内来划分。 $i$ 不在组内 $f[i][j]=f[i-1][j]$，$i$ 组内 $f[i][j]=f[t-1][j-1]+i-t+1$，其中 $t$ 是第 $j-1$ 组中的最小值的下标，二分查找 $t$。

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

using namespace std;

const int N = 5010;

int n, k;
int a[N];
int f[N][N];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k && j <= i; j++) {
            f[i][j] = f[i - 1][j]; // 不选
            int t = lower_bound(a + 1, a + i + 1, a[i] - 5) - a;
            f[i][j] = max(f[i][j], f[t - 1][j - 1] + i - t + 1);
            res = max(res, f[i][j]);
        }
    }
    cout << res << endl;
    return 0;
}

J. CodeForces 176B Word Cut（已补）

题意：每次可以分割字符串，然后把前面一部分接到后面取，给定步数，原串，目标串，问原串经过特定步数能通过多少种方式变成目标串。

妙啊（然而根本想不到

做法：$f[i][0]$ 表示走了 $i$ 步现在为目标串的所有方案数，$f[i][1]$ 表示走了 $i$ 步现在为非目标串的所有方案数。则答案为 $f[k][0]$。

先把原串看成一个环，从任意位置切开，记录能变成目标串的切割数 $cnt$。

如果第 $i$ 步已经成为了目标串，可以从 $f[i-1][0]$ 和 $f[i-1][1]$ 转移。若 $i-1$ 步已经是目标串了，那么第 $i$ 仍然是目标串，只能从 $cnt-1$ 个位置切；若 $i-1$ 步为非目标串，那么就有 $cnt$ 种切法转化为目标串。

如果第 $i$ 为非目标串，可以从 $f[i-1][0]$ 和 $f[i-1][1]$ 转移。若 $i-1$ 步是目标串了，现在要变成非目标串，只能从 $n-cnt$ 个位置切；若 $i-1$ 步为非目标串，现在要保持非目标串，那么就有 $n-1-cnt$ 种切法（首先不能选择 $cnt$ 个会变成目标串的切法，又不能切成自己当前的状态不然就相当于没切）。

数据范围较小，否则需要 KMP 来做第一步的匹配；另外可以用滚动数组优化一下空间。

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

using namespace std;

typedef long long LL;

const int N = 2010, mod = 1e9 + 7;

int n, k;
char a[N], b[N];
LL f[2][2]; // f[i][0]表示第i步变成了b串的方案数,f[i][1]表示第i步变成了非b串的方案数

bool check(int start) {
    bool flag = true;
    for (int i = start, j = 0; i <= start + n - 1; i++, j++) {
        if (a[i] != b[j]) {
            flag = false;
            break;
        }
    }
    return flag;
}

int main() {
    int cnt = 0;
    scanf("%s%s%d", a, b, &k);
    n = strlen(a);
    for (int i = 0; i < n; i++) {
        a[n + i] = a[i];
        if (check(i)) cnt++;
    }
    f[0][!check(0)] = 1; // check为true表示a=b
    for (int i = 1; i <= k; i++) {
        f[i & 1][0] = (f[i - 1 & 1][0] * (cnt - 1) + f[i - 1 & 1][1] * cnt) % mod;
        f[i & 1][1] = (f[i - 1 & 1][0] * (n - cnt) + f[i - 1 & 1][1] * (n - 1 - cnt)) % mod;
    }
    cout << f[k & 1][0] << endl;
    return 0;
}