CodeForces 1107E UVa 10559 (区间 dp 二连击)

发表于 | 分类于 | Views

UVa 10559

题意：

让你对一段数组进行合并，区间内的数都相同就可以做一次合并，每一次合并的贡献是区间长度的平方，让你求出合并完后最大的贡献是多少。

考虑 $dp$。
$dp[i][j][k]$ 表示从 $i$ 位置到 $j$ 位置，$j$ 位置后面还有 $k$ 位和 $a_j$ 相同的数的最大贡献。
先把原数组转化一下，直接把一段相同的合并成一个，$cnt_i$ 表示合并后位置 $i$ 表示原来的几个数，$cc_i$ 表示合并后这个位置的数。

那么转移就有两种：
1、直接把 $a_j$ 和后面 $k$ 位合并
$dp[i][j][k] = dp[i][j-1][0] + (cnt[j] + k)^{2}$
2、令 $i \leq p < j$，$cc_p = cc_j$，就是先把区间 $[p+1,j-1]$ 处理，也就是合并完之后，这个时候 $j$ 和后面的 $k$ 位就会接到位置 $p$，就是处理区间 $[i,p]$ 了。
$dp[i][j][k] = dp[i][p][cnt[j] + k] + dp[p + 1][j - 1][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
69
70
71
72
73
74
75
#include <bits/stdc++.h>
#include <ext/rope>
#include <algorithm>
using namespace __gnu_cxx;
using namespace std;
#define mst(a,b) memset(a,b,sizeof(a))
#define ALL(x) x.begin(),x.end()
#define pii pair<int, int>
#define debug(a) cout << #a": " << a << endl;
#define eularMod(a, b) a < b ? a : a % b + b
#define X first
#define Y second
inline int lowbit(int x){ return x & -x; }
typedef long long LL;
typedef unsigned long long ULL;
const int N = 200 + 10;
const int M = 5e7 + 10;
const int mod = (int) 1e9 + 7;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const double eps = 1e-6;

int n;
int dp[N][N][N];
int cc[N];
int cnt[N];

inline int sqr(int x) {
    return x * x;
}
int solve(int L, int R, int k) {
    if (L == R)
        return sqr(k + cnt[L]);
    int &res = dp[L][R][k];
    if (res)
        return res;
    res = solve(L, R - 1, 0) + sqr(k + cnt[R]);
    for (int i = L; i < R; i++) if (cc[R] == cc[i])
        res = max(res, solve(L, i, k + cnt[R]) + solve(i + 1, R - 1, 0));
    return res;
}

int main() {
#ifdef purple_bro
    freopen("in.txt", "r", stdin);
//    freopen("out.txt","w",stdout);
#endif
    int T;

    scanf("%d", &T);

    for (int cas = 1; cas <= T; cas++) {
        scanf("%d", &n);

        int pre = 0;
        int tot = 0;

        for (int i = 1; i <= n; i++) {
            int v;
            scanf("%d", &v);
            if (v != pre) {
                cc[++tot] = v;
                cnt[tot] = 1;
            } else
                cnt[tot]++;
            pre = v;
        }

        printf("Case %d: %d\n", cas, solve(1, tot, 0));
        mst(dp, 0);
    }

    return 0;
}

CodeForces 1107E

题意：

和上一道题差不多，一个 $01$ 串，也是合并求最大贡献，只不过这道题合并不同的长度的贡献是由另外一个数组提供。

$dp$ 的思路跟上一道题差不多，也是先把原数组处理一下，转移也类似。

合并区间的贡献，可以看出有可能一次性合并一段长的区间的贡献比分几次对这段区间进行合并的贡献小。那我们就先要做一个处理。

$f[i]$ 表示合并一个长度为 $i$ 的区间最多能够获得多少贡献，转移就是
$f[i] = max(f[i], f[i - j] + f[j])$

然后写就是了。

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
#include <bits/stdc++.h>
#include <ext/rope>
#include <algorithm>
using namespace __gnu_cxx;
using namespace std;
#define mst(a,b) memset(a,b,sizeof(a))
#define ALL(x) x.begin(),x.end()
#define pii pair<int, int>
#define debug(a) cout << #a": " << a << endl;
#define eularMod(a, b) a < b ? a : a % b + b
#define X first
#define Y second
inline int lowbit(int x){ return x & -x; }
typedef long long LL;
typedef unsigned long long ULL;
const int N = 100 + 10;
const int M = 5e7 + 10;
const int mod = (int) 1e9 + 7;
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double PI = acos(-1.0);
const double eps = 1e-6;

int n;
char s[N];
char cc[N];
LL f[N];
LL dp[N][N][N];
int cnt[N];

LL solve(int L, int R, int k) {
    if (L == R)
        return f[k + cnt[R]];
    LL &res = dp[L][R][k];
    if (res)
        return res;
    res = solve(L, R - 1, 0) + f[k + cnt[R]];
    for (int i = L; i < R; i++) if (cc[i] == cc[R])
        res = max(res, solve(L, i, k + cnt[R]) + solve(i + 1, R - 1, 0));
    return res;
}

int main() {
#ifdef purple_bro
    freopen("in.txt", "r", stdin);
//    freopen("out.txt","w",stdout);
#endif
    scanf("%d%s", &n, s + 1);

    char ch = '$';
    int tot = 0;

    for (int i = 1; i <= n; i++) {
        if (s[i] != ch) {
            cnt[++tot] = 1;
            cc[tot] = s[i];
        } else
            cnt[tot]++;
        ch = s[i];
    }

    for (int i = 1; i <= n; i++) {
        scanf("%lld", &f[i]);
        for (int j = 1; j < i; j++)
            f[i] = max(f[i], f[i - j] + f[j]);
    }

    printf("%lld\n", solve(1, tot, 0));

    return 0;
}