B - Three Coins¶

题意¶

$N$ 個のマスが一列に並んでおり、左から右に $1$ から $N$ までの番号が振られています。

はじめ、すべてのマスは空です。あなたは、以下の $2$ 種類の操作を任意の順に何度でも行うことができます。

連続する $3$ マスであってコインが置かれていないものを選び、それぞれにコインを置く。
連続する $3$ マスであっていずれにもコインが置かれているものを選び、それぞれからコインを取り除く。

操作を済ませた後、左から $i$ マス目にコインが置かれているなら、 $a_i$ 点が得られます。コインがあるマス全てから得られる点数の合計が、あなたの得点です。

得られる最高得点を求めてください。

解析¶

考虑区间 DP。设 $f_{i,j}$ 和 $g_{i,j}$ 分别表示 $[i,j]$ 区间选/不选的最大收益。

$f_{i,j}=\max\{f_{i,k}+f_{k+1,j}|i\le k<j\}\\ g_{i,j}=\max\{g_{i,k}+g_{k+1,j}|i\le k<j\}$

当 $3\mid(j-i+1)$ 时， $f_{i,j}$ 和 $g_{i,j}$ 也能互相更新。最后答案就是 $f_{1,n}$ 。

实现¶

#include <bits/stdc++.h>

const int maxn = 5e2 + 19;

int n, a[maxn], s[maxn];
int f[maxn][maxn], g[maxn][maxn];

int main(){
    std::scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        std::scanf("%d", a + i), s[i] = s[i - 1] + a[i];
    for(int l = n; l >= 1; --l)
        for(int r = l; r <= n; ++r){
            g[l][r] = s[r] - s[l - 1];
            for(int i = l; i < r; ++i){
                f[l][r] = std::max(f[l][r], f[l][i] + f[i + 1][r]);
                g[l][r] = std::max(g[l][r], g[l][i] + g[i + 1][r]);
            }
            if((r - l + 1) % 3 == 0) f[l][r] = g[l][r] = std::max(f[l][r], g[l][r]);
        }
    std::printf("%d\n", f[1][n]);
}

来源¶

AtCoder Grand Contest 050 B - Three Coins

B - Three Coins¶

题意¶

解析¶

实现¶

来源¶

评论