【道路覆盖】

题目描述

Tar 把一段凹凸不平的路分成了高度不同的 N 段(每一段相同高度),并用 H[i] 表示第 i 段高度。现在 Tar 一共有 n 种泥土可用,它们都能覆盖给定的连续的 k 个部分。
对于第 i 种泥土,它的价格为 C[i],可以使得区间 [i,min(n,i+k-1)] 的路段的高度增加 E[i]。
Tar 要设定一种泥土使用计划,使得使用若干泥土后,这条路最低的高度尽量高,并且这个计划必须满足以下两点要求:
(1)每种泥土只能使用一次。
(2)泥土使用成本必须小于等于 M 。
请求出这个最低的高度最高是多少。

输入格式

第一行为如上文所示的三个正整数:N,M,K。
接下来 N 行,每行3个如上文所示的正整数 H[i],E[i],C[i]。

输出格式

输出有且只有一个数字,为最底部分的高度的最大值。

样例数据 1

输入

4 20 1
1 3 5
1 7 3
4 6 9
3 5 13

输出

3

备注

【数据范围】
对于 30% 的数据:N≤20。
对于 100% 的数据:1≤K≤11;1≤N≤100;0≤M,H[i],E[i],C[i]≤1000000。

首先二分答案,对于分到的高度进行DP看最小费用是否满足条件,这道题要用状态压缩,其中hplus[i][j]代表第i段通过泥土使用能够提升的高度,其中泥土的使用情况用二进制数j来表示,dp[i][j]则是第i段路通过泥土使用到达二分高度的最小花费,j代表i-k到i的路段泥土使用情况,j>>1代表将当前位置0,j >> 1 |( 1 << (k – 1))代表将第k位置1。

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*