JZOJ 3521. 道路覆盖

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

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 //该位选

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #define N 107

 using namespace std;

 int c[N], e[N], h[N], n, m, k;

 int f[N][<<], l, r;

 void Init()

 {

     scanf("%d%d%d", &n, &m, &k);

     for (int i=;i<=n;i++)

         scanf("%d%d%d", &h[i], &e[i], &c[i]);

 }

 bool check(int x){

     memset(f, 0x7f7f7f7f, sizeof(f));

     f[][] = ;

     for (int i = ; i < n; i++)

         for(int j = ; j < ( << k); j++)

             if (f[i][j] != 0x7f7f7f7f)

             {

                 int heigh = ;

                 for (int l = ; l < k; l++)

                     if (j & ( << l)) heigh += e[i - k + l + ];

                 if (heigh + h[i + ] >= x)

                     f[i + ][j >> ] = min(f[i + ][j >> ], f[i][j]);

                 if (heigh + h[i + ] + e[i + ] >= x)

                     f[i + ][(j >> ) | ( << (k - ))] = min(f[i + ][(j >> ) | ( << (k - ))], f[i][j] + c[i + ]);

             }

     for (int i = ; i < ( << k); i++)

         if (f[n][i] <= m) return ;

     return ;

 }

 int main()

 {

     freopen("cover.in", "r", stdin);

     freopen("cover.out", "w", stdout);

     Init();

     l = , r = 1e8;

     while(l < r)

     {

         int mid = (l + r + ) / ;

         if    (check(mid))    l = mid;

         else r = mid - ;

     }

     printf("%d", l);

 }

MinX