mayoko’s diary

プロコンとかいろいろ。

yukicoder No.324 落ちてた閉路グラフ

解法

輪になっているのは, とりあえず直線にするのが典型です。去年のこどふぇす本戦の F 問題とかがそうですね。

輪を直線にするために, 「最初の頂点を選ぶか, 選ばないか」で場合分けをします。
で, 後は dp[now][rest][pre] = (now 番目の頂点を選ぶか選ばないかを考える際に, 残り選ばなければならない頂点数は rest, 直前の頂点が選ばれているかどうかのフラグが pre である際の, 最大スコア) として dp すれば良いです。

const int MAXN = 3003;
const int INF = 1e9;
int dp1[MAXN][MAXN][2];
int dp2[MAXN][MAXN][2];
int w[MAXN];
int n, m;

int dfs1(int now, int rest, int pre) {
    if (now == n) {
        if (rest > 0) return -INF/2;
        if (pre) return w[n-1];
        else return 0;
    }
    int& ret = dp1[now][rest][pre];
    if (ret > -INF) return ret;
    ret = dfs1(now+1, rest, 0);
    if (rest > 0) {
        int tmp = dfs1(now+1, rest-1, 1);
        if (pre) tmp += w[now-1];
        ret = max(ret, tmp);
    }
    return ret;
}
int dfs2(int now, int rest, int pre) {
    if (now==n) {
        if (rest > 0) return -INF/2;
        return 0;
    }
    int& ret = dp2[now][rest][pre];
    if (ret > -INF) return ret;
    ret = dfs2(now+1, rest, 0);
    if (rest > 0) {
        int tmp = dfs2(now+1, rest-1, 1);
        if (pre) tmp += w[now-1];
        ret = max(ret, tmp);
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> w[i];
    if (m == 0) {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k < 2; k++) dp1[i][j][k] = dp2[i][j][k] = -INF;
        }
    }
    // 最初の頂点を入れる
    int ans = dfs1(1, m-1, 1);
    ans = max(ans, dfs2(1, m, 0));
    cout << ans << endl;
    return 0;
}