粉刷木板

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

第 \(i\) 个木匠要么不粉刷，要么粉刷包含木板 \(S_i\) 且长度不超过 \(L_i\) 的连续的一段木板，每粉刷一块可以得到 \(P_i\) 的报酬。不同工匠的 \(S_i\) 不同。 请问如何安排能使工匠们获得的总报酬最多。

\(N\leq 16000\ ,\ M\leq 100\ ,\ S_i\leq 10000\)

题解

设 \(dp(i,j)\) 表示前 \(i\) 个人涂完 \(j\) 个木板的最大答案。

对于第 \(i\) 个人：

1. 若他不涂，则 \(dp(i,j) = dp(i-1,j)\).
2. 若他不涂当前木板，则 \(dp(i,j)=dp(i,j-1)\).
3. 若他涂色，则 \(dp(i,j)=\max \limits_{k\in(0,L_i]\ ,\ j\in[S_i,m]}dp(i-1,j-k)+k\times P_i\).

将3.修改，为：\(dp(i,j)=\max \limits_{k\in[j-L_i.S_i)}dp(i-1,k)+(j-k)\times P_i\).

则：

\[dp(i,j) =\max\left\{\begin{matrix} dp(i-1,j) \\ dp(i,j-1)\\ \max \limits_{k\in[j-L_i.S_i)}\{dp(i-1,k)+(j-k)\times P_i\} \end{matrix}\right. \]

对于以上的第三个式子，我们可以把它移项，变成

\[dp(i,j)= \max\{j\times P_i+dp(i-1,k)-k\times P_i\} \ ,\ k\in[j-L_i,S_i),j\ge S_i \]

发现式子后两项与 \(j\) 无关，可以用单调队列来优化此段最大值。

复杂度 \(O(nm)\) .

代码

#include <bits/stdc++.h>
#define fo(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std;
const int INF = 0x3f3f3f3f,N = 1.6e4+5,M = 105;
typedef long long ll;
typedef unsigned long long ull;
inline ll read(){
	ll ret=0;char ch=' ',c=getchar();
	while(!(c>='0'&&c<='9'))ch=c,c=getchar();
	while(c>='0'&&c<='9')ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
	return ch=='-'?-ret:ret;
}
int n,m;
struct node{int l,p,s;}a[M];
inline bool operator < (const node a,const node b){return a.s < b.s;}
template <typename T> struct dque{
	T a[N]; int st=1,ed=0;
	dque(){st=1,ed=0;}
	inline void clear(){st=1,ed=0;}
	inline bool empty(){return ed-st+1==0;}
	inline int size(){return ed-st+1;}
	inline void push_back(int x){a[++ed] = x;}
	inline T front(){return a[st];}
	inline T back(){return a[ed];}
	inline void pop_back(){ed--;}
	inline void pop_front(){st++;}
	T operator [] (int x){return a[st+x-1];}
};
dque<int>q;
int dp[M][N];
signed main(){
	n = read() , m = read();
	for(int i = 1 ; i <= m ; i ++){
		int l = read() , p = read() , s = read();
		a[i] = (node){l,p,s};
	}
	sort(a+1,a+m+1);
	for(int i = 1 ; i <= m ; i ++){
		q.clear();
		for(int j = max(a[i].s-a[i].l,0) ; j < a[i].s ; j ++){
			while(!q.empty() && dp[i-1][q.back()] - q.back()*a[i].p < dp[i-1][j] - j*a[i].p)
				q.pop_back();
			q.push_back(j);
		}
		for(int j = 1 ; j <= n ; j ++){
			dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
			if(j >= a[i].s){
				while(!q.empty() && q.front() + a[i].l < j) q.pop_front();
				if(!q.empty())dp[i][j] = max(dp[i][j],dp[i-1][q.front()] + (j-q.front())*a[i].p);
			}
		}
	}
	printf("%d",dp[m][n]);
}