SRM 667 div2 hard:ShopPositions
今回の div2 med は div1 easy とほとんど同じっぽいですが, だとするとこの hard は med よりも簡単な気がする…
解法
dp で解きます。
dp[now][preorder][prenum] = (now 番目の店を見ていて, 直前のビルは 1 つのお店につき preorder 番目の利益(つまり p[now-1][preorder-1])をあげていて, 直前のビルが prenum 個のお店を持っている時の, 利益の最大値)
とします。
すると, now 番目のビルが i 個の店を持つことにした際の利益は, (右隣のビルに何個店を置くかは一切考えないとして)
p[now][prenum+i-1] * i + dp[now+1][prenum+i][i]
です。しかし, now-1 番目のビルは now 番目のビルに店を置くことで微妙に損します。この損は
(p[now-1][preorder-1] - p[now-1][preorder+i-1]) * prenum
です。これを引いた分が now 時点での利益です。こんな感じで dp を更新すれば良いです。
const int MAXN = 33; int dp[MAXN][2*MAXN][MAXN]; int n, m; int calc(int now, int num, const vector<vi>& p) { if (num == 0) return 0; return p[now][num-1]; } // po: 直前の店が何番目の値段でやるか // pn: 直前の店の店数 int dfs(int now, int po, int pn, const vector<vi>& p) { if (now == n) return 0; int& ret = dp[now][po][pn]; if (ret >= 0) return ret; ret = 0; for (int i = 0; i <= m; i++) { int tmp = calc(now, pn+i, p) * i + dfs(now+1, pn+i, i, p); if (now > 0 && pn > 0) { tmp -= (calc(now-1, po, p) - calc(now-1, po+i, p)) * pn; } ret = max(ret, tmp); } return ret; } class ShopPositions { public: int maxProfit(int n, int m, vector <int> c) { ::n = n, ::m = m; vector<vector<int> > p(n, vi(3*m)); for (int i = 0; i < n; i++) { for (int j = 0; j < 3*m; j++) p[i][j] = c[3*m*i+j]; } memset(dp, -1, sizeof(dp)); return dfs(0, 0, 0, p); } };