首页 > 其他 > 详细

JZOJ 3521. 道路覆盖

时间:2018-10-21 21:36:38      阅读:135      评论:0      收藏:0      [点我收藏+]

Description

ar把一段凹凸不平的路分成了高度不同的N段,并用H[i]表示第i段高度。现在Tar一共有n种泥土可用,它们都能覆盖给定的连续的k个部分。

对于第i种泥土,它的价格为C[i],可以使得区间[i,min(n,i+k-1)] 的路段的高度增加E[i]。

Tar要设定一种泥土使用计划,使得使用若干泥土后,这条路最低的高度尽量高,并且这个计划必须满足以下两点要求:

(1)每种泥土只能使用一次。

(2)泥土使用成本必须小于等于M。

请求出这个最低的高度最高是多少。

Input

第一行为如上文所示的三个正整数:N,M,K。

接下来N行,每行3个如上文所示的正整数H[i],E[i],C[i]。

Output

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

Sample Input

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

Sample Output

3

做法(转自JZOJ):

二分+状态压缩:
二分枚举最低的高度,接下来考虑判断合法性:设f[i][j]表示在前i位完成j状态的最小金钱代价,那么只要存在状态x使得f[n][x]≤M。然后再考虑状态的转移:注意对于一位i只由它的前k位得到,那么就是说f[i][j]由它的前k位得到,所以j只有k位。k的范围是极小的所以不会超时;要使枚举的最小高度l合法,还要满足该点决策完成之后的高度≥l。然后我们就可以根据条件来进行状态转移:
f[i+1][不选的状态j]=minx(f[i+1][j>>1],f[i][j]); 且要满足最小高度为x //该位不选f[i+1][选之后的状态j]=minx(f[i+1][(j>>1)|(1<<(k-1))],f[i][j]+c[i+1]); 满足“最小高度”为x //该位选

技术分享图片
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #define N 107 
 5 using namespace std;
 6 int c[N], e[N], h[N], n, m, k;
 7 int f[N][1<<12], l, r;
 8 
 9 void Init()
10 {
11     scanf("%d%d%d", &n, &m, &k);
12     for (int i=1;i<=n;i++)
13         scanf("%d%d%d", &h[i], &e[i], &c[i]);
14 }
15 
16 bool check(int x){
17     memset(f, 0x7f7f7f7f, sizeof(f));
18     f[0][0] = 0;
19     for (int i = 0; i < n; i++)
20         for(int j = 0; j < (1 << k); j++)
21             if (f[i][j] != 0x7f7f7f7f) 
22             {
23                 int heigh = 0;        
24                 for (int l = 1; l < k; l++)
25                     if (j & (1 << l)) heigh += e[i - k + l + 1];
26                 if (heigh + h[i + 1] >= x)    
27                     f[i + 1][j >> 1] = min(f[i + 1][j >> 1], f[i][j]);
28                 if (heigh + h[i + 1] + e[i + 1] >= x)
29                     f[i + 1][(j >> 1) | (1 << (k - 1))] = min(f[i + 1][(j >> 1) | (1 << (k - 1))], f[i][j] + c[i + 1]);
30             }
31     for (int i = 0; i < (1 << k); i++)
32         if (f[n][i] <= m) return 1;
33     return 0; 
34 }
35 
36 int main()
37 {
38     freopen("cover.in", "r", stdin);
39     freopen("cover.out", "w", stdout);
40     Init();
41     l = 0, r = 1e8;
42     while(l < r)
43     {
44         int mid = (l + r + 1) / 2;
45         if    (check(mid))    l = mid;
46         else r = mid - 1;
47     }
48     printf("%d", l);
49 }
View Code

 

JZOJ 3521. 道路覆盖

原文:https://www.cnblogs.com/traveller-ly/p/9826733.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!