Algoogle

Algorithm for Programming Contest

AOJ 1086 Live Schedule

Category: AOJ Tag: dp

Live Schedule

問題概要


D日間のライブツアーをC地域でやる.
地域iでj日目にライブをやるときに だけの利益がある.利益が0の場所でライブはしない.
同様に だけ疲れる.
全日程を通して疲労の累計はW以下.
また,ある地域でライブが終わったあと,隣り合う番号の地域で続けてライブを行うことができる.ただし同じ日に同じ地域で2度以上ライブをすることはできない.
さらに,2箇所以上でライブする日はX日以内.
得られる利益の最大はいくらか.

解法


DPする.
dp[i][j][k] := i日目で疲労がj,2箇所以上でライブをしたのがk回のときの最大の利益
ライブをする場所は間に0のない連続する区間.これは累積和を持っておけばO(1)で計算できる.

コード


(1086.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;

#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repi(i,0,n)

inline void chmax(int &x, int y) { x = max(x, y); }
int c, d, w, x, e[32][32], f[32][32], dp[32][64][8], sume[32], sumf[32];

int solve() {
    memset(dp, 0, sizeof(dp));
    rep(i,d) {
        rep(j,c) {
            sume[j+1] = sume[j] + e[i][j];
            sumf[j+1] = sumf[j] + f[i][j];
        }
        rep(j,w+1) rep(k,x+1) {
            chmax(dp[i+1][j][k], dp[i][j][k]);
            rep(l,c) repi(r,l+1,c+1) {
                if(!e[i][r-1]) break;
                int nj = j+sumf[r]-sumf[l], nk = k+(r-l>1);
                if(nj <= w and nk <= x) chmax(dp[i+1][nj][nk], dp[i][j][k]+sume[r]-sume[l]);
            }
        }
    }
    int ans = 0;
    rep(j,w+1) rep(k,x+1) chmax(ans, dp[d][j][k]);
    return ans;
}

bool input() {
    cin >> c >> d >> w >> x;
    rep(i,c) rep(j,d) cin >> e[j][i];
    rep(i,c) rep(j,d) cin >> f[j][i];
    return c or d or w or x;
}

int main() {
    while(input()) cout << solve() << endl;
    return 0;
}

Comments