【YBTOJ】粉刷木板

【YBTOJ】粉刷木板

思路：

设f[i][j]表示到第i个人，涂前j个
所以 f [ i ] [ j ] = m a x ( f [ i − 1 ] [ k ] + ( j − k ) ∗ p [ i ] ) f[i][j]=max(f[i-1][k]+(j-k)*p[i]) f[i][j]=max(f[i−1][k]+(j−k)∗p[i])
用单调队列滚掉 f [ i − 1 ] [ k ] − k ∗ p [ i ] f[i-1][k]-k*p[i] f[i−1][k]−k∗p[i]
然后滚动数组滚掉i

c o d e code code

#include
#include 
#include

using namespace std;

int n, m, f[101010], x[101010], q[101010], w[101010];
struct node
{
	int p, l, s;
}a[101010];

bool cmp(node x, node y)
{
	return x.s					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5690720.html