mayoko’s diary

プロコンとかいろいろ。

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);
    }
};