【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

#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.stl)
				break;
			f[j]=max(f[j], q[hd]+a[i].p*j);
		}
		for(int j=2; j<=m; j++)
			f[j]=max(f[j], f[j-1]);
	}
	printf("%d", f[m]);
	return 0;
}