题目链接
略略略
分析
首先一看到使得最低的高度最高就想到了二分,于是就转化成了一个是否可行的问题
发现这个(k)都很小,考虑使用状态压缩DP
但是我一开始发现似乎并不好设计状态...如果这个(k)表示前(k)个方块的状态有没有开始涂似乎不好转移
看了solution发现我还是(Too Young Too Simple)
我们用对于第(i)块,对它决策有影响的只有它前面的(i-k+1)块的状态,于是我们只需要用一个(k)位二进制串表示状态来从(i)递推到(i+1).对于块(p)二进制串的第(i)位(0位开始)表示第(p-(k-i-1))块的状态
(f[i][s])表示已经从前往后决策完第(i)块,(i-k+1)到(i)的状态为(s)的最小代价,这些状态保证都是合法的(即所有的高度等于等于二分值)
这时候从(i)递推到(i+1)的话我们需要知道之前(i+1)之前(k)块能累高(i+1)块多少高度,这直接扫一遍就好了
如果之前累加的高度(dta)+(h[i+1])大于等于二分的高度,那么我们可以不选涂第(i+1)块
(f[i+1][s>>1]=min(f[i+1][s>>1],f[i][s])),这时候第(k-1)位为0表示(i+1)位没涂
如果(dta+h[i+1]+e[i+1])大于等于二分值,那么我们就可以涂
(f[i+1][s>>1|(1<<(k-1))]=min(f[i+1][s>>1|(1<<(k-1))],f[i][s]+c[i+1]))
意义和第一个类似表示(i+1)位涂的状态
最后判断是否有状态(f[n][s]<=m)就好了
感觉这题还是挺不错的,通过考虑那些状态会影响决策来减小决策空间,表示状态的方法也比较独特(可能是我太菜做的题少)
同时从大佬代码中学到了一个优化就是可行性剪枝,对于(f[i][s])已经大于等于(m)的我们直接不管
代码
/*
code by RyeCatcher
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <utility>
#include <queue>
#include <vector>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <iostream>
#define DEBUG freopen("dat.in","r",stdin);freopen("wa.out","w",stdout);
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define ri register int
#define ll long long
#define ull unsigned long long
#define SIZE 1<<22
using std::min;
using std::max;
using std::priority_queue;
using std::queue;
using std::vector;
using std::pair;
using namespace __gnu_pbds;
inline char gc(){
static char buf[SIZE],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
template <class T>inline void read(T &x){
x=0;int ne=0;char c;
while((c=gc())>'9'||c<'0')ne=c=='-';x=c-48;
while((c=gc())>='0'&&c<='9')x=(x<<3)+(x<<1)+c-48;x=ne?-x:x;return ;
}
const int maxn=1005;
const int inf=0x7fffffff-1926817;
int f[maxn][1<<11];
int S,n,m,k;
int h[maxn],c[maxn],e[maxn];
inline bool chk(int qwq){
for(ri i=0;i<=n;i++)for(ri j=0;j<S;j++)f[i][j]=inf;
f[0][0]=0;
int num=0;
for(ri o=0;o<n;o++){
for(ri i=0;i<S;i++){
if(f[o][i]>m)continue;//优化
num=0;
for(ri j=1;j<k;j++){
if(o-(k-j)+1<=0)continue;
if(i&(1<<j))num+=e[o-(k-j)+1];
}
if(num+h[o+1]>=qwq){
f[o+1][i>>1]=min(f[o+1][i>>1],f[o][i]);
}
if(num+h[o+1]+e[o+1]>=qwq){
f[o+1][i>>1|(1<<(k-1))]=min(f[o+1][i>>1|(1<<(k-1))],f[o][i]+c[o+1]);
}
}
}
for(ri j=0;j<S;j++)if(f[n][j]<=m)return 1;
return 0;
}
int main(){
int ans=0;
FO(cover)
read(n),read(m),read(k);
for(ri i=1;i<=n;i++){
read(h[i]),read(e[i]),read(c[i]);
}
S=1<<k;
int mid,L=0,R=1e6+5;
while(L<=R){
mid=(L+R)>>1;
if(chk(mid))ans=mid,L=mid+1;
else R=mid-1;
}
printf("%d
",ans);
return 0;
}