Typical DP Contest - L 猫

L: 猫 - Typical DP Contest | AtCoder

• 普通に dp すると TLE するが式変形をすると間に合うタイプ

class l_cat {
public:
    void solve(void) {
            int N;
            cin>>N;

            vector<vector<int>> f(N, vector<int>(N,0));
            REP(i, N)
            REP(j, N)
                cin>>f[i][j];

            //
            // dp[i][j] := 猫iまで並べたとき、i番目の猫から距離1以内にいる猫のうち
            //             最も小さい番号がjであるようなときの幸福度の総和の最大値
            //
            // dp[i+1][j] のとき、 j<=l<=i+1 は i+1 と 1 以内の位置にあるので
            //                              i+1
            // dp[i+1][j] = max{dp[i][k] + 2*∑ f[i+1][l] | k <=j }
            //                              l=j
            //
            // (dp[i][i] = max{dp[i-1][k] | k <= i-1} であることに注意)
            //
            // となる。 (2 倍なのは猫 i,j 双方からの親密度を計算するため)
            //
            // このままだと更新に O(N^3) かかってしまうが
            //
            //                i
            //  Sum[i][j] = 2*∑ f[i][l] とすると
            //               l=j
            //
            // dp[i+1][j] = max{dp[i][k] + Sum[i+1][j] | k <= j }
            //            = max{max{dp[i][k] | k<=j-1}, dp[i][j]} + Sum[i+1][j]
            //            = max{max{dp[i][k] + Sum[i+1][j-1] - Sum[i+1][j-1] | k <= j-1 },
            //                  dp[i][j]} + Sum[i+1][j]
            //            = max{dp[i+1][j-1]-Sum[i+1][j-1], dp[i][j]} + Sum[i+1][j]
            //
            // 計算量は O(N^2)
            //
            const int inf = (1<<30);
            vector<vector<ll>> sum(N+1,vector<ll>(N+1,0));
            vector<vector<ll>>  dp(N+1,vector<ll>(N+1,-inf)); // f[i][j] < 0 なるケースもあるので -inf で初期化
            dp[0][0] = 0;

            // 和を事前計算しておく
            REP(i, N)
            for (int j = i; j >= 0; --j)
                sum[i][j] = sum[i][j+1] + 2*f[i][j];

            REP(i, N)
            for (int j = 0; j <= i+1; ++j) // dp[i][i] も計算する
            {
                dp[i+1][j] = dp[i][j];
                if (j >= 1)
                    dp[i+1][j] = max(dp[i+1][j], dp[i+1][j-1]-sum[i+1][j-1]);
                dp[i+1][j] += sum[i+1][j];
            }

            ll res = 0;
            REP(i, N)
                res = max(res, dp[N-1][i]);
            cout<<res<<endl;
    }
};