SRM 691 Div1 Medium Moneymanager
X = 0 であるときは、a/b が大きい方が前に来るようにすればよい。
前半・後半に分ける集合を固定したときも、それぞれの集合内では、a/b が大きい方が前に来るのが最適となっている。
あとは、前半・後半にどう分けるかが問題となるのだが、a/b でソートして、後半部分の b の合計を固定すると DP で計算することができる。
自分の実装では、a/b で降順にソートし、前半・後半部分の後ろから敷き詰めていくような DP で解いた。(4 次元の状態数を持つことになるので MLE に注意する)
計算量は、O(N^4*maxB^2)で、少しだけシビアなので、あまり定数倍が重くなりすぎないようにする。
ll dp[2][30][260][260]; class Moneymanager { public: int getbest(vector <int> a, vector <int> b, int X) { int n = a.size()/2; vector<P> v(2*n); rep(i, 2*n) v[i] = P(a[i], b[i]); auto f = [&](const P &i, const P &j){ return i.fst*j.snd<j.fst*i.snd;}; sort(all(v), f); ll sum = 0; mset(dp, -1); rep(k, 260) dp[0][0][0][k] = 0; rep(i, 2*n){ int t = i%2; mset(dp[!t], -1); for(int j = 0; j <= min(i, n); j++){ for(int k = 0; k < 260; k++){ for(int l = 0; l <= k; l++){ if(dp[t][j][l][k]<0) continue; chmax(dp[!t][j][l][k], dp[t][j][l][k]+(sum-l+k+v[i].snd)*v[i].fst); if(l+v[i].snd<=k) chmax(dp[!t][j+1][l+v[i].snd][k], dp[t][j][l][k]+(l+v[i].snd)*(v[i].fst)); } } } sum += v[i].snd; } ll res = -INF; rep(i, 300){ if(dp[0][n][i][i]>=0) chmax(res, dp[0][n][i][i]+X*i); } return res; } };