POJ 1821

Problem link

This is a classic problem about maintaining a monotonic queue. I have been solving POJ problems recently, so I am recording it here.

There are $K$ workers and $N$ boards. Each worker can paint at most $L_i$ consecutive boards, and the interval must include board $S_i$. Painting each board earns $P_i$. Find the maximum total income.

Dynamic programming: $DP[i][j]$ is the maximum income after the first $i$ workers paint $j$ boards. Then

$DP[i][j] = max(dp[i-1][j],dp[i][j-1], dp[i-1][k] + peo[i].pay*(j-k))$

Here, $dp[i-1][k] + peo[i].pay*(j-k)$ means that the first $i-1$ workers paint $k$ boards and worker $i$ paints the next $j-k$.

Observe that $dp[i-1][k] + peo[i].pay*(j-k) = dp[i-1][k] - peo[i].payk + peo[i].payj$. The first part, $dp[i-1][k] - peo[i].pay*k$, can be handled with a monotonic queue.

int n,k;
struct po {
    int len;
    int st;
    int pay;
}peo[200];

bool cmp(po p1,po p2) {
    return p1.st < p2.st;
}

int dp[105][17000];
deque<int>q;

void solve() {
    sa(n),sa(k);
    repp(i,1,k) {
        sa(peo[i].len);
        sa(peo[i].pay);
        sa(peo[i].st);
    }
    sort(peo+1,peo+k+1,cmp);

    repp(i,1,k) {
        q.push_front(max(0,peo[i].st-peo[i].len));
        repp(j,1,n) {
            dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            if(j >= peo[i].st + peo[i].len)continue;
            while(!q.empty() && q.front() + peo[i].len < j) 
                q.pop_front();

            if(j < peo[i].st) {
                int t = dp[i-1][j] - peo[i].pay*j;
                while(!q.empty() &&  dp[i-1][q.back()] - peo[i].pay*q.back()< t)
                    q.pop_back();

                q.push_back(j);
                continue;
            }
            int ans = 0;
            if(!q.empty())
                ans = dp[i-1][q.front()] + peo[i].pay*(j-q.front());

            dp[i][j] = max(dp[i][j],ans);
        }
    }
    printf("%d\n",dp[k][n]);
}