No.31 悪のミックスジュース

DP + 貪欲法の切り替え問題。
解法を理解するの時間がかかった。要復習問題ですな。
dp のメモリ確保結果がたりなくて (vector dp(m*N+1, 0); とかして) で RE になってしまった。
class EvilMixJuice {
public:
    void solve(void) {
            int N;
            ll  V;
            cin>>N>>V;
            vector<ll> C(N);
            REP(i,N)
                cin>>C[i];

            if (V <= N)
            {
                // 全てのジュースを 1 リットルずつ買って等分をまぜればよいだけ
                cout<<accumulate(RANGE(C),0LL)<<endl;
                return;
            }
            //
            // のこり V リットル分を
            //
            // p[0]>=p[1]>=...>=p[N-1]>=0
            // p[0]+...+p[N-1] = V
            //
            // なるように最小コストで買えばよい。
            //
            // 通常の dp でやると O(N*V) となってしまい TLE する。
            //
            // そこで S[i] = C[0]+...+C[i] として
            // (i+1) リットルをコスト S[i] で購入すると考える。
            //
            // 単価 S[i]/(i+1) が最小の (i+1,S[i]) を目一杯買えばよさそう。
            // ただし (i+1) の倍数リットルの購入だと過不足が生じてしまう。
            //
            // S[i]/(i+1) が最小の i を minI , m = (minI+1) とするとき
            // (m,S[m-1]) パック以外のパックをどれだけ買えばよいかを DP で計算する。
            //
            // m*k リットル買うとすると (k,S[k-1]) を m 個買うよりは安い
            // ので (m,S[m-1]) 以外の (k,S[k-1]) の購入総数は最大 m までと考えてよい
            //
            // このとき minI!=k のすべての (k,S[k-1]) の購入総量は最大 m*N となる。
            //
            // (1,S[0]) が最小の 1 リットルパックなので各 (k,S[k-1]) は最大 m*N 個買うことになる。
            //
            // よって時間計算量 O(m^2*N^2) <= O(N^4)
            //
            // 購入総数が m を超えてしまうなら (m,S[m-1]) パック 1 個におきかえればよいので
            // (m,S[m-1]) 以外のパックの購入総数は最大 m 未満である。
            //
            // よって O(N^3) で計算できる。
            //
            vector<ll> S(N,0);
            S[0] = C[0];
            FOR(i,1,N)
                S[i] = S[i-1]+C[i];

            // 必ず 1 リットル以上は買うので先に計算しておく
            V = max(0LL, V-N);

            // S[i]/(i+1) が最大となる minI を求める
            ll minI = -1;
            ll minS = (1<<30);
            REP(i,N)
            {
                if (minS*(i+1) >= S[i]*(minI+1)) // minS/(minI+1) >= S[i]/(1+i)
                {
                    minI = i;
                    minS = S[i];
                }
            }
            ll m   = minI+1;
            ll mN2 = max(m*N+1, V-(V-m*N)/m*m+1); // 参照用の V-(V-m*N)/m*m+1 を忘れずに

            // dp[i][j] := i 番目までの S を使って j リットル買うときの最小コスト
            vector<ll> dp(mN2+1,0);

            dp[0] = 0;
            for (ll i = 0; i < mN2; ++i)
                dp[i+1] = dp[i] + S[0]; // dp[i][j+1] = dp[i][j] + S[0]

            // O(N^3)
            for (ll i = 0; i < N; ++i)
            for (ll j = 0; j <= mN2; ++j)
            {
                ll k = min(mN2, j+(i+1));
                dp[k] = min(dp[k], dp[j]+S[i]);
            }
            // V のうち m*(N+1) までは dp で計算した結果を使う。
            // 残りを (m,S[m-1]) パックで買えるだけ買う
            ll  kk = max(0LL,(V-m*N)/m);
            cout<<kk*S[m-1]+dp[V-kk*m]+S[N-1]<<endl;
    }
};