AcWing 298. 围栏 (POJ1821)

标签：include   超过   Painter   clu   中间   描述   函数   时间复杂度   mes   

标签（空格分隔）： dp 单调队列优化

题目描述

有N块木板从左到右排成一行，有M个工匠对这些木板进行粉刷，每块木板至多被粉刷一次。

第 i 个木匠要么不粉刷，要么粉刷包含木板 \(S_i\) 的，长度不超过 $ L_i $ 的连续的一段木板，每粉刷一块可以得到 $ P_i $ 的报酬。

不同工匠的\(S_i\)不同。

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

输入格式

第一行包含两个整数N和M。

接下来M行，每行包含三个整数Li,Pi,Si。

输出格式

输出一个整数，表示结果。

数据范围

1≤N≤16000,
1≤M≤100,
1≤Pi≤10000

输入样例：

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

输出样例：

17

显然，这是一道单调队列优化的模板题。

首先，我们考虑这个单调队列。

什么是单调队列 ？

单调队列， 指的是一个保存当前状态的决策点集合的队列。 队列的队首即是当前的最优决策。但在状态转移的过程中，需要不断维护。时间复杂度为O（阶段数 * 状态数）

维护单调队列有两种方式。

1. 检查队首的合法性
2. 在队尾删除无用决策

提一嘴，这里的单调是k单调递增，calc（i，k）单调递减

首先， 这一题有三个原始状态状态：

1. 第i个painter什么也不刷， 即f[i - 1,j]
2. 第j块板子不刷，即f[i, j - 1]
3. 第i个工匠粉刷 k + 1 到 j 块板子 。
   由题面得: 该工匠粉刷不超过Li块，且必须刷Si，所以需要满足 :
   \[ k + 1
   所以有状态转移方程 :
   \[ f[i, j] = \max_{ j - L_i \leqslant k \leqslant S_i - 1} \{ f[i - 1, k] + P_i * (j - k) \} \] 显然，在决策的过程中 \(P_i * j\) 是一个“等效”的常量， 所以将原转移方程改写为 :
   \[ f[i, j] = P_i * j + \max_{ j - L_i \leqslant k \leqslant S_i - 1} \{ f[i - 1, k] - P_i * k \} \]
   其中， 我们就可以把 \(f[i - 1, k] - P_i * k\) 写成下文的calc函数
   剩下的和着代码一起讲。

#include
using namespace std;
const int maxn = 16000 + 5;
const int maxm = 100 + 5; 
int n, m; 
int Queue[maxn];// 单调队列本体
struct node {
    int l, p, s;
}painter[maxm];
//代表每个粉刷匠的l,p,s
int f[maxm][maxn];
//f[i][j] : 代表考虑第i位粉刷匠刷到第j块板子(中间可以有不刷的)能get的最大报酬 
int calc(int i, int k){
    return f[i - 1][k] - painter[i].p * k;
}
bool cmp(node a, node b){
    return a.s = painter[i].s){
                while(h 

AcWing 298. 围栏 (POJ1821)

标签：include   超过   Painter   clu   中间   描述   函数   时间复杂度   mes   

原文地址：https://www.cnblogs.com/yangxuejian/p/11361304.html