希丰展？使Md
by dhclient_eth1 @ 2021-03-03 18:54:49
希丰展？[使Md](https://www.luogu.com.cn/blog/luogu/how-to-use-markdown)
by syanoeclipse @ 2021-03-03 19:07:03
@[幽理家的男人](/user/292029) 同问
感觉这样转移下来不显然是两个一起转移吗？
这样只转移一半感觉是错误的
但是我两个一起转移就只有 75pts 可还行 ...
by Glori @ 2021-06-05 14:12:44
@[Repo](/user/128387)
好久以前做的了，刚刚看了一下，发现是自己以前sb了。题解是对的，不过有点误导性。
我一开始的问题应该也是对的，它更新完的余量应该就是就是``` g[i]-a[j] ```，题解里面虽然写的是取max，但是实际上只要``g[i]>=a[j] && f[i | (1<<(j-1))]>f[i]``
`` g[i]-a[j] ``就是大于``g[i | (1<<(j-1))]``的，因为不可能``i | (1<<(j-1))``状态下，它所需要的电梯又多，余量有大（余量大的话，那么``f[i | (1<<(j-1))]``必然是可以减小的），所以题解是对的。我语言功底不大好，也不知道你能不能看懂QAQ。
你的代码我看了，少讨论了一种情况,这么写就ac了，因为当``g[i]>=a[j] && f[i | (1<<(j-1))]==f[i]``
成立时，余量时要取max的。
```cpp
if(leav[i]>=wei[j]&&dp[i|(1<<(j-1))]>dp[i]) {
dp[i|(1<<(j-1))]=dp[i];
leav[i|(1<<(j-1))]=leav[i]-wei[j];
}
else if(leav[i]>=wei[j]&&dp[i|(1<<(j-1))]==dp[i]){
dp[i|(1<<(j-1))]=dp[i];
leav[i|(1<<(j-1))]=max(leav[i|(1<<(j-1))],leav[i]-wei[j]);
}
else if(leav[i]<wei[j]&&dp[i|(1<<(j-1))]>dp[i]) {
dp[i|(1<<(j-1))]=dp[i]+1;
leav[i|(1<<(j-1))]=w-wei[j];
}
```
by 幽理家的男人 @ 2021-06-05 15:11:39
@[幽理家的男人](/user/292029) 谢谢您！
后来我也发现了这个问题，就是当 dp 数组的值相等时，但是 leav 数组的情况却是原本的剩余更优，那么就有了第三种情况。
题解应该就是偷懒然后合并到了两个操作里面，但是理论上第二种情况里面是不存在 `=` 的情况的，也就是不存在上面的特殊情况。
by Glori @ 2021-06-05 15:28:43
再加上本来的限制条件就是“装得下”，那么显然有 `leav[i']` 不比 `leav[i]` 优，所以这样合并成一个操作应该是没有问题的，个人是这么理解的，还是谢谢你的回复！
我一开始找了半天没有找到我自己代码里面的错误，后来看了题解一直不明白，现在终于明白了。
by Glori @ 2021-06-05 15:32:27