POJ1821 Fence 题解报告

传送门

1 题目描述

A team of $k (1 <= K <= 100) $workers should paint a fence which contains $N(1<=N<=16000)$ planks numbered from $1$ to $N$ from left to right. Each worker $i(1<=i<=K)$ should sit in front of the plank $S_i$ and he may paint only a compact interval (this means that the planks from the interval should be consecutive). This interval should contain the Si plank. Also a worker should not paint more than Li planks and for each painted plank he should receive $P_i(1<=P_i<=10000)$. A plank should be painted by no more than one worker. All the numbers Si should be distinct.

Being the team’s leader you want to determine for each worker the interval that he should paint, knowing that the total income should be maximal. The total income represents the sum of the workers personal income.

Write a program that determines the total maximal income obtained by the K workers.

有 $N$ 块木板从左至右排成一行,有 $K$ 个工匠对这些木板进行粉刷,每块木板至多被粉刷一次。第 $i$ 个工匠要么不粉刷,要么粉刷包含木板 $i$ 的,长度不超过$L_i$的连续一段木板,每粉刷一块木板可以得到$P_i $的报酬。

求如何安排能使工匠们获得的总报酬最多。

输入

The input contains:
Input

N K
L1 P1 S1
L2 P2 S2
…
LK PK SK

Semnification

N -the number of the planks; K ? the number of the workers
Li -the maximal number of planks that can be painted by worker i
Pi -the sum received by worker i for a painted plank
Si -the plank in front of which sits the worker i

输出

The output contains a single integer, the total maximal income.

样例

样例输入1

 8 4
 3 2 2
 3 2 3
 3 3 5
 1 1 7

样例输出1

 17

提示

Explanation of the sample:
the worker 1 paints the interval [1, 2];
the worker 2 paints the interval [3, 4];
the worker 3 paints the interval [5, 7];
the worker 4 does not paint any plank

2 思路

2.1 暴力无优化

先将所有工匠按照Si从小到大排序

• 状态：f[i][j]，前 i 个工匠粉刷前 j 块木板(允许为空)的最大报酬。
• 状态转移方程：

1. 第$i$个工匠什么都不刷：$f[i][j]=f[i-1][j]$

2. 第$j$块木板可以空着不刷：$f[i][j]=f[i][j-1]$

3. 考虑第$ i $个工匠粉刷第 $k+1j$块，

𝑓[𝑖][𝑗] =𝑚𝑎𝑥{𝑓[𝑖 − 1][𝑘] + 𝑃𝑖 ∗ (𝑗 − 𝑘)},其中𝑗−𝐿𝑖≤𝑘≤𝑆𝑖−1，𝑗 ≥ 𝑆𝑖

枚举$i$,$j$,$k$，时间复杂度为$O(n^{2}k)$

因为我们可以看到数据并没有那么小:$1<=K<=100$， $1<=N<=16000$

显然就不行

以呢，我们考虑用优先队列优化

2.2 优先队列优化dp

优化：𝑓[𝑖][𝑗] =𝑚𝑎𝑥{𝑓[𝑖 − 1][𝑘] + 𝑃𝑖 ∗ (𝑗 − 𝑘)}，其中𝑗 ≥ 𝑆𝑖，𝑗−𝐿𝑖≤𝑘≤𝑆𝑖−1
• 将最外层循环i看作定值，考虑内层循环 j 和决策 k ，转换得到：
• 𝑓[𝑖][𝑗] = 𝑃𝑖 ∗ 𝑗 +𝑚𝑎𝑥{𝑓[𝑖 − 1][𝑘] − 𝑃𝑖 ∗ 𝑘)}，其中𝑗−𝐿𝑖≤𝑘≤𝑆𝑖−1，𝑗 ≥ 𝑆𝑖

维护一个决策点k单调递增，数值 $f[i-1][k]-Pi\times k$单调递减的队列，

只有这个队列中的决策才有可能成为某一刻的最优决策

• 单调队列支持：

1. 当 j 变大时，检查队头，将小于j-Li的出队。

2. 查询最优决策时，队头为所求最大值

3. 新决策入队时，检查队尾$f[i-1][k]-Pi\times k$的单调性，无用决策出队，新
   决策入队

2 具体实现

• 对于每一个外层循环i，

当内层循环开始时($j=S_i$)，建立一个空的单调队列，

将区间 $[max(j-Li,0),Si-1]$的决策加入到单调队列中，执行3

• 对于每一个$j=SiN$，

先检查队头是否合法(1)，再取队头为最优策略(操作2)进行状态转移，再进行入队(3)

总时间复杂度为O(NK)

code

#include<bits/stdc++.h>
using namespace std;
const int N=2e4+2,K=1e2+2;
struct node{
    
    int l,s,p;
}a[K];
bool cmp(node x,node y){
    
	return x.s<y.s;
}
int f[K][N],q[N],n,k;
int main(){
    
    while(~scanf("%d%d",&n,&k)){
    
        for(int i=1;i<=k;i++) {
    
        	scanf("%d%d%d",&a[i].l,&a[i].p,&a[i].s);
        }
        sort(a+1,a+k+1,cmp);
        memset(f,0,sizeof(f));
        for(int i=1;i<=k;i++){
    
            int hd=0,tl=0;
            q[tl++]=max(0,a[i].s-a[i].l);
            for(int j=1;j<=n;j++){
    
                f[i][j]=max(f[i-1][j],f[i][j-1]);
                if(j>=a[i].s+a[i].l) continue;
                while(hd<tl&&q[hd]+a[i].l<j) hd++;
                if(j>=a[i].s) f[i][j]=max(f[i][j],f[i-1][q[hd]]+a[i].p*(j-q[hd]));
                else{
    
                    int x=f[i-1][j]-j*a[i].p;
                    while(hd<tl&&f[i-1][q[tl-1]]-q[tl-1]*a[i].p<x) tl--;
                    q[tl++]=j;
                } 
            }
        }
        printf("%d\n",f[k][n]);
    }
    return 0;
}

完结撒花*

·*,°*:.*(￣▽￣)/$:.°* 。