题解 P4138 【[JOISC2014]挂饰】
空の軌跡
2019-04-29 19:41:31
# 这是一道有操作的 01背包 问题
## 思路：
通过思考，我们可以想到无论运算过程中是否缺少钩子，但只要
最终结果剩余的钩子不小于 0 也就是不缺少钩子，就满足要求，因为我们可以通过改变挂钩的顺序来使得过程中不会出现缺少挂钩的情况，因此，我们可以 **忽略挂饰顺序所带来的影响** 。
用 **maxx [ i ] 表示 还剩 i 个挂钩时所能获取的最大喜悦值** , 然后就利用 **01背包** 的转移 (如果不会背包请先简单的学习一下) 。
最终结果显然就是 **max{ maxx [ 0 ~ INF ] }** 。
## 处理数组越界的情况：
1≤N≤2000 ，0≤Ai≤N(1≤i≤N)
可以看到挂钩最多可以有大约2000 × 2000 = 4000000 个，显然我们不能开这么多数组来一个一个转移 , 要不然就 T 了。
通过观察我们看到 N 只有2000 ，也就是最多只会使用 2000 个钩子，所以当计算到钩子数超过2000的转移，我们直接把结果的钩子数量当做2000来看，因为2000就是极限了，这并不会影响答案。
## 注意：
为了应对负数的情况，我让 **maxx [ ] 的下标全部增加 2000** ，这样就可以表示在负数范围内的值了。
## 转移：
有人在讨论中讨论可不可以转一维 ，不知是不是在讨论转移的问题 ，对此我们只要判断 Ai 是否小于 1 就行了 。
如果 Ai >= 1 说明安装此挂饰后剩余挂钩的数量不会减少，那我们反向枚举转移 ，可以保证不会重复选择该挂饰 。
反之则正向枚举转移 ，也可以保证不会重复选择（请和 **完全背包** 区别开 ，这两个的 **正向枚举** 有本质上的区别）
如果某些情况下的转移难以处理，导致出锅，而我们又没有解决的办法。那么就需要使用更多的状态，为了优化空间，我们可以使用滚动数组优化内存，像分组背包中就可以使用这种操作。
## 初始化：
把所有的 maxx [ ] 赋值为-INF，将 maxx [ 2001 ] 赋值为 0 , 这样在转移的时候就可以判断是否存在为当前挂钩数量的情况 ，如果不存在也就是 **maxx[ ] == -INF** , 这就可以直接 continue 了。
# 代码：
```
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int maxx[4010];
int main()
{
int n,a,b;cin>>n;
memset(maxx,-0x3f,sizeof(maxx)); // 初始化
maxx[2001]=0;
for(int i=1;i<=n;i++)
{
cin>>a>>b;
--a; // 自己占用钩子
if(a>0) // a>0 则反向枚举转移
{
for(int j=4000;j>=0;j--)
{
if(maxx[j]==-0x3f3f3f3f)continue; // 目前不存在的情况
if(j+a>=4000) // 如果超越了上限，那就直接向上限转移
maxx[4000]=max(maxx[j]+b,maxx[4000]);
else maxx[j+a]=max(maxx[j]+b,maxx[j+a]); // 否则常规转移
}
}
else // a<=0 则正向枚举转移
{
for(int j=0;j<=4000;j++)
{
if(maxx[j]==-0x3f3f3f3f)continue; // 同上
maxx[j+a]=max(maxx[j]+b,maxx[j+a]);
}
}
}
int ans=0;
for(int i=2000;i<=4000;i++) // 选择出一个最大的答案
ans=max(maxx[i],ans);
cout<<ans;
}
```
# 结束