Poj1821 fence problem solving Report

Portal

1 Title Description

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.

Yes $N$ The planks line up from left to right , Yes $K$ A craftsman painted the boards , Each board shall be painted at most once . The first $i$ A craftsman either doesn't paint , Either the whitewash contains wood $i$ Of , Length not exceeding $L_i$ A continuous piece of wood , Each piece of painted wood can get $P_i $ The reward for .

Ask how to arrange to make the craftsmen get the maximum total remuneration .

Input

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

Output

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

Examples

The sample input 1

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

Sample output 1

 17

Tips

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 Ideas

2.1 Violence without optimization

First of all, all the craftsmen should follow Si Sort from small to large

• state ：f[i][j], front i A craftsman before painting j A board ( Allow null ) The maximum reward for .
• State transition equation ：

1. The first $i$ A craftsman does nothing ：$f[i][j]=f[i-1][j]$

2. The first $j$ A piece of wood can be left empty without painting ：$f[i][j]=f[i][j-1]$

3. Consider the $ i $ A craftsman painted the first $k+1j$ block ,

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

enumeration $i$,$j$,$k$, The time complexity is $O(n^{2}k)$

Because we can see that the data is not so small :$1<=K<=100$, $1<=N<=16000$

Obviously not

So , We consider optimizing with priority queues

2.2 Priority queue optimization dp

Optimize ：𝑓[𝑖][𝑗] =𝑚𝑎𝑥{𝑓[𝑖 − 1][𝑘] + 𝑃𝑖 ∗ (𝑗 − 𝑘)}, among 𝑗 ≥ 𝑆𝑖,𝑗−𝐿𝑖≤𝑘≤𝑆𝑖−1
• Loop the outermost layer i Regarded as fixed value , Consider inner circulation j And decision making k , Convert to get ：
• 𝑓[𝑖][𝑗] = 𝑃𝑖 ∗ 𝑗 +𝑚𝑎𝑥{𝑓[𝑖 − 1][𝑘] − 𝑃𝑖 ∗ 𝑘)}, among 𝑗−𝐿𝑖≤𝑘≤𝑆𝑖−1,𝑗 ≥ 𝑆𝑖

Maintain a decision point k Monotone increasing , The number $f[i-1][k]-Pi\times k$ Monotonic decline Queues ,

Only the decision in this queue can be the best decision at a certain moment

• Monotonic queue support ：

1. When j When it gets bigger , Inspection team leader , Will be less than j-Li Out of the team .

2. When querying the optimal decision , The team leader is the maximum value

3. When new decisions join the team , Check the tail of the team $f[i-1][k]-Pi\times k$ The monotonicity of , Useless decisions come out of the team , new
   Make a decision to join the team

2 Concrete realization

• For each outer loop i,

When the inner loop starts ($j=S_i$), Create an empty monotone queue ,

The interval $[max(j-Li,0),Si-1]$ The decision is added to the monotone queue , perform 3

• For each of these $j=SiN$,

First, check whether the team leader is legal (1), Then take the team leader as the optimal strategy ( operation 2) Make a state transition , Then join the team (3)

The total time complexity is zero 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;
}

End of the flower *

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