POJ1821 Fence 题解报告

传送门

A team of $k (1 <= K <= 100) $workers should paint a fence which contains \(N (1 <= N <= 16 000)\) 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 <= 10 000)\). 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.

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

 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

先将所有工匠按照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+1~j\)块，