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

 

Data Constraint

对于30%的数据：N≤20。

对于100%的数据：1≤K≤11，1≤N≤100，0≤M,H[i],E[i],C[i]≤1000000。

分析

首先看数据范围，k那么小差不多就是状态压缩了

最小值最大，显然二分

我们二分最小高度，DP判断

（然鹅比赛的时候蠢到没有想到第i位由前k位影响？）

在display_lzy大爷机(you)缘(yi)巧(gao)合(zhi)之下，想到了上面括号里的内容

设f[i][s]为前i段和前k种泥土的状态为s时满足最小值也大于等于二分值的最小代价

如何维护高度？

设h[i][s]为从第i中往前数k种泥土的状态为s时的能增加的高度，然后如果当前位高度加上这个也小于二分值的话就不合法，f[i][s]=Inf

然后显然只能从s>>1和s>>1 + 1<<k-1转移过来

最后找f[n][s]中有没有小于等于m的就行了 

 

#include 
      
       #include 
       
        #include 
        
         using namespace std;const int N=110;int n,m,k;int h[N],e[N],c[N],mh=2147483647,sh,sumh,mxbit;int f[N][1<<12],h1[N][1<<12];bool Solve(int height) {    memset(f,0x7f,sizeof f);    memset(h1,-0x7f,sizeof h1);    f[0][0]=h1[0][0]=0;    for (int i=1;i<=n;i++)        for (int j=0;j<=mxbit;j++) {            int from1=j>>1,from2=(j>>1)+(1<
         
          >1;        if (Solve(mid)) ans=max(ans,mid),l=mid+1;        else r=mid-1;    }    printf("%d",ans);}