「POJ1821」Fence

题意：有一排墙编号从 $1$ 至 $n$，有 $k$ 个工人要粉刷这面墙，第 $i$ 个人在第 $s _i$ 位置上，手有 $l _i$ 长(即最多只能粉刷长度为 $l _i$ 的墙，粉刷的墙必须是连续一段)，并且必须刷当前位置这面墙(即第 $s _i$ 面墙必须被粉刷)，第 $i$ 个人每刷一面墙获得的收入为 $p _i$ 元，现在请你合理安排 $k$ 个工人的工作(每面墙不可以被粉刷 $2$ 次，当然也可以选择不刷，也可以选择某个工人不刷)，求获得的最大收益。

DP 啊。

用 $f[i][j]$ 表示前 $i$ 个人刷前 $j$ 面墙的最大收益，可以推出状态转移方程如下：

$$f[i][j]=\max(f[i][j],f[i-1][j])$$

即第 $i$ 个工人不工作。

$$f[i][j]=\max(f[i][j],f[i][j-1])$$

即第 $j$ 面墙不刷。

$$f[i][j]=\max(f[i][j],f[i-1][k]+p _i\times (j-k))(k+1\le j,k+ l _i\ge i)$$

即第 $i$ 个人从第 $k+1$ 面墙刷到第 $j$ 面墙。

但是还是太慢了，考虑优化第三个转移方程，可以得到：

$$f[i][j]=\max(f[i][j],f[i-1][k]-p _i\times k+p _i\times j))(k+1\le j,k+ l _i\ge i)$$

其中遍历 $j$ 的时候可以直接算出 $p _i\times j$，主要优化 $f[i-1][k]-p _i\times k$，单调队列！！

基本操作一波即可，注意一开始先按 $s _i$ 给工人从小到大排序，$f[k][n]$ 即是答案。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<ctime>
#define INF 1e9
using namespace std;
const int maxn=16101,maxk=110;
int n,k;
int head,tail;
int f[maxk][maxn];
struct queue
{
	int val;
	int pos;
}q[maxn];//单调队列，维护最大f[i-1][k]-p[i]*k
struct worker
{
	int l;
	int p;
	int s;
}a[maxk];
int cmp(worker a,worker b)
{
	return a.s<b.s;
}
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++)
		scanf("%d%d%d",&a[i].l,&a[i].p,&a[i].s);
	sort(a+1,a+k+1,cmp);
	for(int i=1;i<=k;i++)
	{
		head=1;
		tail=0;
		for(int j=max(0,a[i].s-a[i].l);j<a[i].s;j++)//把之前的状态先加进去
		{
			int num=f[i-1][j]-a[i].p*j;
			while(head<=tail&&q[tail].val<num)
				tail--;
			q[++tail].val=num;
			q[tail].pos=j;
		}
		for(int j=1;j<=n;j++)
		{
			f[i][j]=max(f[i-1][j],f[i][j-1]);//第i个人不涂或第j面墙不涂
			if(j<a[i].s||j>=a[i].s+a[i].l)//超出限制
				continue;
			while(head<=tail&&q[head].pos+a[i].l<j)//删除范围外的
				head++;
			if(head<=tail)
				f[i][j]=max(f[i][j],q[head].val+a[i].p*j);
		}
	}
	printf("%d",f[k][n]);
	return 0;
}