题目链接
略略略
分析
首先一看到使得最低的高度最高就想到了二分,于是就转化成了一个是否可行的问题
发现这个$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$的我们直接不管
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
#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\n",ans);
return 0;
}
|