POJ 1821 Fence 【DP+单调队列】

tonyfang posted @ 2016年4月02日 14:46 in poj with tags c++ OI , 835 阅读

设$f[i,j]$表示 第i个粉刷匠 刷到第j个墙的最大花费

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

f[i,j] = max{f[i-1, k] + (j-k)*p[i].p} (p[i].s - p[i].l<= k < p[i].s) 

那么我们发现,那个取max的似乎可以用单调队列搞?

max{f[i-1, k] - k*p[i].p} + j * p[i].p

然后就可以愉快地单调队列啦

 

# include <stdio.h>
# include <algorithm>
# include <queue>
using namespace std;

int n, k;
struct fence {
	int l, p, s;
	bool operator < (const fence& a) const {
		return s < a.s;
	}
}p[120];

struct pqd {
	int v, pos;
	pqd() {}
	pqd(int _v, int _pos) : v(_v), pos(_pos) {}
	bool operator < (const pqd &a) const {
		return v < a.v || (v == a.v && pos > a.pos);
	}
};

priority_queue<pqd> q;

int f[120][16010];
// f[i,j] 表示 第i个人,刷到j墙的最大值
// f[i,j] = max(f[i,j-1], f[i-1,j]);
// f[i,j] = max{f[i-1, k] + (j-k)*p[i].p} (p[i].s - p[i].l<= k < p[i].s) 
// max{f[i-1, k] - k*p[i].p} + j * p[i].p;

int main() {
	scanf("%d%d", &n, &k);
	for (int i=1; i<=k; ++i) scanf("%d%d%d", &p[i].l, &p[i].p, &p[i].s);
	sort(p+1, p+k+1);
	for (int i=1; i<=k; ++i) {
		while(!q.empty()) q.pop();
		for (int j=max(0, p[i].s-p[i].l); j<p[i].s; ++j) {
			pqd t(f[i-1][j] - j * p[i].p, j);
			q.push(t);
		}
		for (int j=1; j<=n; ++j) {
			f[i][j] = max(f[i-1][j], f[i][j-1]);
			if(j < p[i].s || j >= p[i].s + p[i].l) continue;
			while(!q.empty() && q.top().pos < j - p[i].l) q.pop();
			if(q.empty()) continue;
			f[i][j] = max(f[i][j], q.top().v + j*p[i].p);
		}
	}
	printf("%d\n", f[k][n]);
	return 0; 
}
pavzi.com 说:
2023年5月17日 19:14

Pavzi Post is a startup founded by dedicated webmasters and bloggers who want to produce engaging material that is truthful, fascinating, and worth reading. We are more of a digital community where you can pavzi.com find various information, resources, and subjects about current events or news. With the assistance of the editorial and content teams, we supply you with the best web content on any topic imaginable.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter