题解 CF924E 【Wardrobe】
SIGSEGV
2020-01-29 10:16:31
令$H=\sum_{i=1}^na_i$,将重要盒子的底端在$[l,r]$内转换为重要盒子的顶端在$[L,R]$内，其中$L=H-r,R=H-l$。
同时可得出最佳答案的至少一种方案中所有重要的盒子一定会连在一起。
然后考虑背包。背包中选中的物品代表从下往上放，未被选中的物品代表它们最后放，这样算出来的值不会比实际情况少。这样背包是正确的，因为最佳答案肯定会被统计到。
显然不重要盒子必须先做背包且它们的做背包顺序对答案没有影响，然而重要的盒子要按照$a_i$从大到小的顺序做背包，因为在所有选中的重要盒子内把低的放在高的上面一定更优。（有些选中的盒子因为**高度不够**不能统计入答案，这些高度不够的显然用$a_i$大的去垫更好）
算法时间复杂度为$O(nH)$。但是CF的题解中说珂以优化到$O(H\sqrt{H})$，这个菜鸡不会，知道怎么优化的珂以发评论qwq
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 10005;
int n,dp[N],l,r;
struct Box {int v,tp;} a[N];
int main ()
{
ios::sync_with_stdio(false);
cin >> n >> l >> r;int sum = 0;
for (int i = 1;i <= n;i++) cin >> a[i].v,sum += a[i].v;
for (int i = 1;i <= n;i++) cin >> a[i].tp;
sort(a + 1,a + n + 1,
[](Box a,Box b) {return a.tp < b.tp || (a.tp == b.tp && a.v > b.v);});
int tmp = l;l = sum - r;r = sum - tmp;
for (int i = 1;i <= sum;i++) dp[i] = INT_MIN >> 2;
dp[0] = 0;
for (int i = 1;i <= n;i++)
for (int j = sum;j >= a[i].v;--j)
dp[j] = max(dp[j],dp[j - a[i].v] + a[i].tp * (l <= j && j <= r));
cout << *max_element(dp + 1,dp + sum + 1) << endl;
return 0;
}
```