文档章节

poj 1821 - dp,单调队列

m2012
 m2012
发布于 2012/06/02 23:21
字数 1127
阅读 454
收藏 0
终于做出这题了!泪流满面啊。

首先,要理解清楚题目意思。有一道线性篱笆由N个连续的木板组成。你手上有K个工人,你要叫他们给木板涂色。每个工人有3个字段:L 表示 这个工人可以涂的最大木板数目,S表示这个工人站在哪一块木板,P表示这个工人每涂一个木板可以得到的钱。要注意的是,工人i可以选择不涂任何木板,否则,他的涂色区域必须是连续的一段,并且S[i]必须包含在内。 最后还有,每块木板只能被涂一次。

理解完题目意思后,很容易联想到邮局模型。所以看看能不能用类似的方程解决。
设f(i,j)表示使用前i个工人来对前j个木板进行涂色。
由这题,学到最重要 经验就是,一定要把every细节都想清楚才开始code,不然自找麻烦。
先看看我们要计算哪些状态,也就是每一维的值域。对于i,范围应该是[0...K],对于每个i,j的范围应该是[0....N]
马上可以看到边界条件是 当i == 0或者 j==0的时候,f(i,j)=0

然后现在假设 i 和 j 都不为0。
如果j < s[i] , 显然,这时候f(i,j) = f(i - 1,j)
如果j >= s[i],并且 j - s[i] + 1 < L[i]。这种情况,表示的是,工人先可以从木板s[i]开始向右连续 j - s[i] + 1涂个木板,然后工人可以决定向左涂0...L[i] - (j -s[i] +1)个木板,所以,这个时候的转移方程为:

(#) f(i,j) = f(i-1,j) 或者 min { f(i-1,t) + P[i] * (s[i] - (t + 1) + 1) } + P[i] *(j -(s[i] + 1) + 1)

对于某个元组(i,j,t),这个方程的含义是,先由前i-1个工人给前t个木板涂色,然后工人i给木板t+1.....木板j进行涂色。然后,t是受到 j 和 s[i] 的约束的,必须满足j - (t + 1) + 1 <= L
为什么我们要把转移发成写成那样子呢?
想想我们编程的时候是怎么安排计算顺序的:
for i = 0 to K
for j = 0 to N
计算f(i,j)

当我们在最内层循环计算f(i,j)的时候,我们可以认为i是一个常数,这样的话,当我们把转移方程写成(#)那样子的话,我们就成功把j和t分开,这样子,我们就可以在不同的状态之间共享方程里相同的一部分,而且,我们可以发现,t的上下限都是不减的,于是,我们就可以使用单调队列了。

记得,写代码之前,在纸上,画个图,清清楚楚地弄明白各个量的关系,初始值,约束等等!
千万别一上来就coding,搞清楚细节先!


看看最后一种情况,如果j >= s[i],并且 j - s[i] + 1 > L[i],这时候的方程是很显然的:
f(i,j) = f(i-1,j)或者 f(i-1,s[i] - 1) + P[i] * L[i]

记得排序啊

 

#include <deque>
#include <algorithm>
#include <utility>
#include <cstdio>
#include <cassert>
using namespace std;


typedef pair<int, int> PairII;

inline int dist(int start, int end) { return end - start + 1; }

template<class DQ>
void pushElem(DQ & q, PairII p) {
	while (!q.empty() && q.back().second <= p.second) q.pop_back();
	q.push_back(p);
}

struct Worker {
	int L, S, P;
};

bool cmpWorker(const Worker & a, const Worker & b) {
	return a.S < b.S;
}

deque<PairII> Q;
int N, K;
int f[101][16001];
Worker a[101];

void dp() {
	int i, j;

	for (i = 0; i <= K; ++i) {
		int t = 0;
		for (j = 0; j <= N; ++j) {
			int & ans = f[i][j];
			ans = 0;
			if (i == 0) {
				ans = 0;
			} else if (j == 0) {
				ans = 0;
			} else if (j < a[i].S) {
				ans = f[i - 1][j];
			} else if (a[i].S <= j && dist(a[i].S, j) < a[i].L) {
				ans = f[i - 1][j];
				int rest = a[i].L - dist(a[i].S, j);
				int left = max(0, a[i].S - rest - 1);
				while (t <= a[i].S - 1) { pushElem(Q, make_pair(t, f[i - 1][t] + a[i].P * dist(t + 1, a[i].S))); t += 1; }
				while (!Q.empty() && Q.front().first < left) Q.pop_front();
				if (!Q.empty()) { ans = max(ans, Q.front().second + dist(a[i].S + 1, j) * a[i].P); }
			} else if (dist(a[i].S, j) >= a[i].L) {
				ans = max(f[i - 1][j], f[i - 1][a[i].S - 1] + a[i].L * a[i].P);
			} else {
				assert(0);
			}
		}
	}
}

void input() {
	scanf("%d %d", &N, &K);
	int i, j;
	for (i = 1; i <= K; ++i) {
		scanf("%d %d %d", &(a[i].L), &(a[i].P), &(a[i].S));
	}

	//因为尼玛忘记排序,wa了好多次!!!
	sort(a + 1, a + K + 1, cmpWorker);
}

int main() {
	input();
	dp();
	printf("%d\n", f[K][N]);
	return 0;
}

© 著作权归作者所有

共有 人打赏支持
上一篇: poj3017 开个坑
下一篇: POJ2373 - 单调队列
m2012
粉丝 16
博文 129
码字总数 52548
作品 0
广州
程序员
私信 提问
加载中

评论(2)

m2012
m2012

引用来自“shyJohnni”的评论

请教下楼主诶,
1. Line50,i往左最多可以涂left个木板,t的范围为什么不是0~left,而是0~s[i[呢?
2.Line53, 当i往右尽最大力涂L个木板也还没够着 j 的时候,如过i涂必定会在j木板前留下一些空隙,而i-1个工人由于要连续的限制涂不到这些木板,所以为什么还要尝试去涂?而不是把任务交给前面的i-1个人期望他们能涂到那么远? 是因为题目没要求一定要每个木板都涂上吗?
3.单调序列的优化我不是太懂,这样跟我计算手工计算每种可能计算最大值来比较取最优有什么优化吗?看样子好像是每种可能都被计算了啊?
关于单调序列的优化能不能麻烦您推荐点资料看看?谢啦。

1. f(i, t)里的t,表示前i个工人给前面1~t个木板涂色,t是位置,不是数量,所以不是0~left。
2. 没看明白你的意思。反正就两种情况,工人i要么出手,要么不出手。如果工人i选择了出手,他必定尽最大努力向右涂。如果他不出手,就转移为f(i-1,j)。不用多想特殊情况。
3. 单调队列的优化就是,减少重复的计算,复杂度可以降低一维。资料可以自行百google:)
s
shyJohnni
请教下楼主诶,
1. Line50,i往左最多可以涂left个木板,t的范围为什么不是0~left,而是0~s[i[呢?
2.Line53, 当i往右尽最大力涂L个木板也还没够着 j 的时候,如过i涂必定会在j木板前留下一些空隙,而i-1个工人由于要连续的限制涂不到这些木板,所以为什么还要尝试去涂?而不是把任务交给前面的i-1个人期望他们能涂到那么远? 是因为题目没要求一定要每个木板都涂上吗?
3.单调序列的优化我不是太懂,这样跟我计算手工计算每种可能计算最大值来比较取最优有什么优化吗?看样子好像是每种可能都被计算了啊?
关于单调序列的优化能不能麻烦您推荐点资料看看?谢啦。
12.9 省选训练总结3(2) DP的优化

目录 数据结构优化 维护前面的DP的最小最大值,使得不需要循环一边去找寻更新值。 滑窗 最重要的一种数据结构优化。维护一个最值单调双端队列,区间单调移动的时候只需要加入维护/弹出元素即...

OwenOwl
2017/12/10
0
0
栈与队列-单调栈,单调队列

什么时候使用? 单调栈 在均摊O(1) 即总时间复杂度为O(n)内实现找到某数右边第一个比它大(小)的数 单调队列 滑窗问题 在运行的过程中能够快速寻求前k个或后k个中最大或最小的值 我们直接来...

weixin_40777696
2017/12/13
0
0
12.8~12.9题解

今天主要写一下题解,总结待整理好后另开一篇发表(大约是明天)。 题面见各大OJ。本次题解都是讨论对于已经列好的DP方程的优化。 【HDU3401】 单调队列优化要求参数分离和枚举区间单调。对于...

myjs999
2017/12/10
0
0
POJ 2533: Longest Ordered Subsequence

题目在此 解题思路:很简单的动规。 设序列长度为 N,每步状态 dp[i] (0 <= i <= n - 1) 为 [0...i] 区间使用 i 所能组成的最长单调递增子序列的长度。 动规条件: 初始状态设 1(因为 a[i]...

Alexander_zhou
2014/03/04
0
0
dp优化 12 - 09

数据结构优化 单调队列优化 其中 双端队列队列,队列内保存之后可能成为最优值的值,保证有单调性。 特点是转移范围有限制。 真·数据结构优化 当 没有单调性时,就可以用线段树之类的数据结...

aziint
2017/12/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

rabbitmq安装教程

RabbitMQ有Windows与Linux版本的,这里先写Windows版本的安装。 以前安装软件总是在百度上找某某安装教程,结果能按照教程安装好的软件真的不多。想起先前以为大牛说的一句话,去官网按照官网...

em_aaron
今天
6
0
Android 贝塞尔曲线实践——波浪式运动

一、波浪效果如下 贝塞尔曲线自定义波浪效果的案例很多,同样方法也很简单,大多数和本案例一样使用二次贝塞尔曲线实现,同样还有一种是PathMeasure的方式,这里我们后续补充,先来看贝塞尔曲...

IamOkay
今天
2
0
Nmap之防火墙/IDS逃逸

选项 解释 -f 报文分段 --mtu 指定偏移大小 -D IP欺骗 -sI 原地址欺骗 --source-port 源端口欺骗 --data-length 指定发包长度 --randomize-hosts 目标主机随机排序 --spoof-mac Mac地址欺骗 ...

Frost729
今天
2
0
带你搭一个SpringBoot+SpringData JPA的环境

不知道大家对SpringBoot和Spring Data JPA了解多少,如果你已经学过Spring和Hibernate的话,那么SpringBoot和SpringData JPA可以分分钟上手的。 其实我在学完SpringBoot和SpringData JPA了之...

java菜分享
今天
7
0
Chocolatey 在Window搭建一个开发环境

在看了(利用 Chocolatey 快速在 Windows 下搭建一个开发环境)后,准备从零开始 一、准备工作 1、用管理员权限启动:powershell,执行错误请参考(PowerShell因为在此系统中禁止执行脚本的解...

近在咫尺远在天涯
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部