刘宇轩题解。

不加 Markdown 不会写，洛谷题解写习惯了，就写带 $\LaTeX$ 的题解吧。

如果按这个思路感觉有点上位蓝了。

首先说结论。按以下式子排序后 $i$ 较小的更优：

$$s_i+w_i\le s_{i+1}+w_{i+1}$$

考虑证明。

看洛谷题解把这种贪心叫「微扰」，就是证明我们交换相邻两个数后一定不劣即可。

假设我们当前考虑 $i$ 和 $i+1$ 两个位置。

不交换时：

• $i$ 位置剩余的载重量：$$s_i-\sum_{j=1}^{i-1}w_j$$
• $i+1$ 位置剩余的载重量：$$s_{i+1}-\sum_{j=1}^{i}w_j$$

交换后：

• $i$ 位置剩余的载重量：$$s_i-\sum_{j=1}^{i-1}w_j-w_{i+1}$$
• $i+1$ 位置剩余的载重量：$$s_{i+1}-\sum_{j=1}^{i-1}w_j$$

不交换时对答案的贡献（仅考虑 $i$ 和 $i+1$）：

$$\min\{s_i-\sum_{j=1}^{i-1}w_j,s_{i+1}-\sum_{j=1}^{i}w_j\} $$

交换后对答案的贡献：

$$\min\{s_i-\sum_{j=1}^{i-1}w_j-w_{i+1},s_{i+1}-\sum_{j=1}^{i-1}w_j\} $$

把第一个记作 $\text{A}$ 式，第二个记作 $\text{B}$ 式。

我们只需要证明 $\text{A}\le\text{B}$，即可证明交换后答案不劣于交换前。

我们考虑枚举 $\text{A}$ 和 $\text{B}$ 的每一种情况。

为了方便观察，我们将 $\text{A}$ 和 $\text{B}$ 都加上：

$$\sum_{j=1}^{i+1}w_j$$

得到：

$$\text{A}=\min\{s_i+w_i+w_{i+1},s_{i+1}+w_{i+1}\}$$ $$\text{B}=\min\{s_i+w_i,s_{i+1}+w_i+w_{i+1}\}$$

分类讨论如下（$\text{A}\le\text{B}$）

• $\text{A}=s_i+w_i+w_{i+1}$，$\text{B}=s_i+w_i$

  由于 $\text{A}>\text{B}$，不满足假设条件，舍去。

• $\text{A}=s_{i+1}+w_{i+1}$，$\text{B}=s_i+w_i$

  因为我们假设 $\text{A}\le\text{B}$，故得到 $s_i+w_i≥ s_{i+1}+w_{i+1}$。

• $\text{A}=s_i+w_i+w_{i+1}$，$\text{B}=s_{i+1}+w_i+w_{i+1}$

  既然我们 $\text{B}=s_{i+1}+w_i+w_{i+1}$，又因为 $\text{B}=\min\{s_i+w_i,s_{i+1}+w_i+w_{i+1}\}$，故 $s_i+w_i≥s_{i+1}+w_i+w_{i+1}$，故 $s_i+w_i≥s_{i+1}+w_{i+1}$。

• $\text{A}=s_{i+1}+w_{i+1}$，$\text{B}=s_{i+1}+w_i+w_{i+1}$

  同上，交换 $\text{B}$ 的值，我们得到 $s_i+w_i≥s_{i+1}+w_{i+1}$。

故 $\text{A}\le\text{B}\Rightarrow s_i+w_i≥s_{i+1}+w_{i+1}$。

由该式，我们得到 $\text{A}=s_{i+1}+w_{i+1}$。

显然 $\text{B}$ 不论取哪个值，$\text{A}\le \text{B}$ 一直成立。

故 $s_i+w_i≥s_{i+1}+w_{i+1}\Rightarrow \text{A}\le\text{B}$。

故 $\text{A}\le\text{B}\Leftrightarrow s_i+w_i≥s_{i+1}+w_{i+1}$。

证毕。

#include <bits/stdc++.h>
using namespace std;
const int N = 30, M = (1 << 25) + 10;
int n, h, dp[M], ans = -1, x[M];//dp[i]表示i状态下的承受量; x[i]记录i状态下的高度 
struct node {
	int h, w, s;
} a[N];
bool cmp(node x, node y) {
	return x.w + x.s < y.w + y.s;//i较小的将更优 
}
int main() {
	scanf("%d%d", &n, &h);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d%d", &a[i].h, &a[i].w, &a[i].s);
	}
	sort(a + 1, a + n + 1, cmp);
	dp[0] = 1e9;//方便底下取min时，初始状态永远不会被转移到 
	for (int i = 1; i < (1 << n); i++) {
		int lst = __builtin_ffs(i);//取出i的第一个1，根据我们前面的推论，i较小的一定最优 
		x[i] = x[i ^ (1 << (lst - 1))] + a[lst].h;
		dp[i] = min(dp[i ^ (1 << (lst - 1))] - a[lst].w, a[lst].s);
		if (x[i] >= h) ans = max(ans, dp[i]);//如果dp是负数也没有关系，因为那代表不合法，不会影响ans的答案 
	}
	if (ans != -1) printf("%d", ans);
	else printf("Impossible");
	return 0;
} 

状压暴力是 $O(n2^n)$ 的，我们不讲。

假设我们能够贪心的把整个序列先排个序，然后放积木的先后顺序就按照其在排序后的顺序摆放，则可做到 $O(2^n)$ 转移。

本题解用于证明邻项交换的正确性。

能够证明，邻项交换的偏序关系可表示为有序二元组，即：

定义有序二元组 $(a,b)$，其中 $a,b\in \N^+$，定义其偏序关系为：

$$(a,b)<(c,d)\Leftrightarrow \min(a-d,c)<\min(a,c-b) $$

我们需要证明其是良序的。

1. $a=c$，则原式 $\Leftrightarrow d> b\Leftrightarrow a+b<c+d$
2. $a<c$，则 $\min(a-d,c)=a-d$，则原式 $\Leftrightarrow a-d<c-b\Leftrightarrow a+b<c+d$
3. $a>c$，则 $\min(a,c-b)=c-b$，则原式 $\Leftrightarrow a-d<c-b<c\Leftrightarrow a+b<c+d$

于是二元组偏序关系等价于 $a+b<c+d$，显然良序，证毕。

update on 26.09.10:

我发现了我的复杂度比别人多一个 $n$，也就是说，我是卡过去的。

SOLUTION

看到 $n \le 25$ 发现这个不大能直接暴力 dp，于是我们换个思路。

假如我们已经定好了要把集合 $S$ 里的元素放到这个大厦里，怎么放是最优的？

猜一下估计是一个贪心吧。

发现相邻两个积木的顺序不会影响他们前面或者后面所有元素的稳定值，于是我们可以试着邻项交换证一下。

于是通过非常简单的证明，得到一个式子：min(s-k.w,k.s)>min(k.s-w,s)。这个直接扔到重载的 $<$ 里面就行。

具体方法不说了。

发现这个有传递性，于是不需要对每一个集合排序，而是对全体积木排序就行了。

于是我们排序，枚举所有 $state \in [0,2^n-1]$，求出答案。

发现做完了，还是不难的。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
int T,n,H;
struct node{
    int h,w,s;
    bool operator<(const node &k)const{
        return min(s-k.w,k.s)>min(k.s-w,s);
    }
}a[30];
#define lowbit(x) (x&(-x))
short mp[16777217];
signed main(){
    freopen("block.in","r",stdin);
    freopen("block.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>H;
    for(register int i=1;i<=n;i++){
        cin>>a[i].h>>a[i].w>>a[i].s;
    }
    for(int i=0;i<25;i++){
        mp[1<<i]=i+1;
    }
    sort(a+1,a+1+n);
    int ans=-1;
    for(register int i=1;i<(1<<n);i++){
        int s=i,hi=0,ms=1e18,t;
        while(s){
            t=mp[lowbit(s)],s-=lowbit(s),hi+=a[t].h,ms=min(ms-a[t].w,a[t].s);
        }
        if(hi<H||ms<0) continue;
        ans=max(ans,ms);
    }
    if(ans==-1) cout<<"Impossible\n";
    else cout<<ans<<'\n';
    return 0;
}

注：笔者发现了一种神奇的方法，使用 $lowbit$ 运算加速了枚举，有一点优化吧。

用以下代码进行测试发现快 $0.5$倍左右。

TESTCODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
int T,n,m;
int ppc(int x){
    int r=0;
    while(x) r+=(x&1),x>>=1;
    return r;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int ans=0;
    for(int i=1;i<=33554431;i++){
        ans+=ppc(i);
    }
    cout<<ans<<'\n';
    return 0;
}