CODE THANKS FESTIVAL 2018 G - Sum of Cards

問題ページ

解法

頂点のグラフで考える．枚目のカードの表に，裏に が書かれている場合，頂点 と頂点 の間に辺を引く．問題文の条件をこのグラフ上に言い換えると，

• 表裏を選ぶ操作→各辺を向き付けする．
• 種類以上の整数が見える→出次数が1以上の頂点がk個以上にする．
• 見えている数の和の最大化→ 頂点 から出ている辺の本数 の最大化

となる． は順列になっていることから，このグラフは全頂点の次数が2で，各連結成分は一つのサイクルになっている．各サイクルごとに 種類使ったときに達成しうる最大値が計算できれば，あとはナップサックDPの要領で 種類以上の数が見えるときの和の最大値を求められる．したがって，各サイクルごとに 種類使ったときに達成しうる最大値を計算する方法を考える．

この問題では であることから 程度の大きさのDPテーブルは持てる．このような問題では 番目までで 種類使ったときの最大値 というような状態の持ち方が定石となる．このようにDPテーブルを保持したときに 番目の頂点間の辺の向き付けに対応する遷移がどのようになるか考える． 番目の頂点から 番目の頂点に向き付けされていて， 番目から 番目へ向き付けする場合のみ，種類数 が増加しない．よって種類数が増加するかどうかの判定のためには，直前の辺の向きをDPテーブルに持っておけば可能となる．サイクルの最後の頂点についての辺の向き付けで種類数が増加するかの判定を行うためには，サイクルの最初の頂点と最後の頂点の間の辺の向きをDPテーブルに持っておけば可能となる．

よって
サイクルの 番目までで 種類の数を使い直前の辺の向きが で最初の頂点と最後の頂点の辺の向きが のときの和の最大値
というDPテーブルを持つことで 番目の頂点間の辺の向き付けに対応する遷移を実現できる．具体的な遷移はソースコードを見てください．

まとめると，

• グラフを構築してサイクルに分割
• サイクルごとにDPして 種類の数を使ったときの和の最大値を求める
• ナップサックDPでサイクルごとの値をまとめて最終的な答えを求める

とすればよい．

これ500点ってマジ？？？

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a) {
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'[';
    for(const T &i: a) out<<i<<',';
    out<<']';
    return out;
}
template<class T>
ostream &operator <<(ostream& out, const set<T>& a) {
    out<<'{';
    for(const T &i: a) out<<i<<',';
    out<<'}';
    return out;
}
template<class T, class S>
ostream &operator <<(ostream& out, const map<T,S>& a) {
    out<<'{';
    for(auto &i: a) out<<i<<',';
    out<<'}';
    return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

ll dp[5010][5010][2][2], x[5010][5010];
signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n, K;
    cin >> n >> K;
    vector<ll> a(n), b(n);
    REP(i, n) cin >> a[i], a[i]--;
    REP(i, n) cin >> b[i], b[i]--;

    vector<vector<ll>> g(n);
    REP(i, n) {
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }

    ll idx = 0;
    vector<vector<ll>> vs;
    vector<bool> used(n);
    function<void(ll)> dfs = [&](ll v) {
        used[v] = true;
        vs[idx].push_back(v+1);
        for(auto to: g[v]) {
            if(!used[to]) dfs(to);
        }
    };
    REP(i, n) {
        if(!used[i]) {
            vs.push_back(vector<ll>());
            dfs(i);
            idx++;
        }
    }

    memset(dp, -1, sizeof(dp));
    idx = 0;
    vector<vector<ll>> dp2(vs.size());
    for(auto v: vs) {
        // サイクルvについてDP
        const ll m = v.size();
        dp[0][1][1][1] = v[m-1];
        dp[0][1][0][0] = v[0];
        FOR(i, 1, m) FOR(j, 1, m+1) REP(k, 2) {
            if(dp[i-1][j][0][k] != -1) {
                chmax(dp[i][j][1][k], dp[i-1][j][0][k] + v[i-1]);
                if(i==m-1 && k==1) {
                    chmax(dp[i][j][0][k], dp[i-1][j][0][k] + v[i]);
                } else {
                    chmax(dp[i][j+1][0][k], dp[i-1][j][0][k] + v[i]);
                }
            }
            if(dp[i-1][j][1][k] != -1) {
                chmax(dp[i][j+1][1][k], dp[i-1][j][1][k] + v[i-1]);
                if(i == m-1 && k==1) {
                    chmax(dp[i][j][0][k], dp[i-1][j][1][k] + v[i]);
                } else {
                    chmax(dp[i][j+1][0][k], dp[i-1][j][1][k] + v[i]);
                }
            }
        }
        // dp2[i番目のサイクル][j種類使った] = 和の最大値
        dp2[idx].resize(v.size()+1);
        REP(i, m) REP(j, 2) REP(k, 2) {
            chmax(dp2[idx][i+1], dp[m-1][i+1][j][k]);
        }
        idx++;
        // dpの初期化
        REP(i, m) FOR(j, 1, m+1) REP(k, 2) REP(l, 2) {
            dp[i][j][k][l] = -1;
        }
    }

    // ナップサックDPの要領で連結成分ごとの値をまとめる
    memset(x, -1, sizeof(x));
    x[0][0] = 0;
    REP(i, dp2.size()) REP(j, K+1) REP(k, dp2[i].size()) {
        if(x[i][j] == -1) continue;
        chmax(x[i+1][min(j+k, K)], x[i][j] + dp2[i][k]);
    }
    cout << x[vs.size()][K] << endl;

    return 0;
}