Dp
题目背景
SOURCE：NOIP2015-SHY-10
题目描述
一块土地有 n 个连续的部分，用 H[1]，H[2]，…，H[n] 表示每个部分的最初高度。有 n 种泥土可用，他们都能覆盖连续的 k 个部分，第 i 种泥土的价格为 C[i]，可以使 i，i+1，…，i+k-1 部分的高度增加 E[i]（如果 i+k>n，那就覆盖 i，…，n ），我们必须满足以下条件：
1、每种泥土只能使用一次。
2、成本必须小于等于 m 。
要求在上述条件下，使得最低的部分的高度尽量高，请求出这个高度。
输入格式
第一行三个整数 n，m，k，表示土地有几个部分，最大预算成本以及每种泥土能覆盖的部分数。
接下来 n 行，每行三个整数 H[i]，E[i]，C[i]。
输出格式
输出一个整数，表示在满足条件的情况下，最低部分的高度的最大值。
样例数据 1
输入
4 20 1
1 3 5
1 7 3
4 6 9
3 5 13
输出
3
备注
【数据范围】
对 30% 的输入数据：1≤n≤20 。
对 100% 的输入数据：1≤k≤11；1≤n≤100；0≤m；H[i],E[i],C[i]≤10^6 。
一看题就知道要二分，关键在于怎么check（考试的时候没想出来）。
本来想写个搜索骗个分的，结果发现有点慢，就换了个贪心+搜索，仍然只有30pts233，虽然得分点跟别人不一样。。。
所以说整体思路就出来了，二分答案，然后状压每个人的前k个人的选取情况转移就行了，如果最后在满足所有人都大于mid的情况下总花费最小值是不超过m的说明情况合法。
代码：
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int n,m,k,h[105],e[105],c[105],sum[105][2050],l=0x3f3f3f3f,r,mk,f[105][2050],bit[15],ans;
inline bool check(int mid){
memset(f,0x3f3f3f3f,sizeof(f));
f[0][0]=0;
for(int i=1;i<=n;++i){
int pos=min(k,i),up=bit[pos];
bool ff=false;
for(int j=0;j<up;++j){
if(sum[i][j]+h[i]<mid)continue;
f[i][j]=min(f[i][j],f[i-1][(j>>1)]+(j&1?c[i]:0));
f[i][j]=min(f[i][j],f[i-1][((j>>1)|bit[pos-1])]+(j&1?c[i]:0));
if(f[i][j]>m)f[i][j]=0x3f3f3f3f;
else ff=true;
}
if(!ff)return false;
}
for(int i=0;i<=mk;++i)if(f[n+1][i]<=m)return true;
return true;
}
int main(){
n=read(),m=read(),k=read();
int pos,up;
for(int i=0;i<=k;++i)bit[i]=1<<i;
for(int i=1;i<=n;++i){
h[i]=read(),e[i]=read(),c[i]=read(),pos=min(k,i),up=bit[pos];
for(int j=0;j<up;++j){
for(int t=0;t<pos;++t)
sum[i][j]+=(j&bit[t]?e[i-t]:0);
}
}
l=0,r=1000000005;
while(l<=r){
int mid=l+r>>1;
if(check(mid))l=mid+1,ans=mid;
else r=mid-1;
}
cout<<ans;
return 0;
}