算法板子的扩大化思路（长期更新）
数字量偏移的01背包
思路：
1.DP的想法
- Q： 为啥要用01背包而不是其它算法？
- A：我们发现，每只奶牛只有选和不选两种状态，而且是需要决策的，所以01背包绝对是最好的选择
01背包中，一定要想好什么是体积，什么是价值，什么是背包容量。此题中，我们可以把体积看成奶牛的智商，背包容量看成奶牛的个数，价值看成奶牛的情商。每只牛有两种选择：参加会展和不参加会展。我们要求在智商一定的情况下情商的最大值，这其实就是01背包的模板。状态转移方程的推导如下：
- 第 i 只奶牛不参加会展：$dp[i][j]=dp[i−1][j]$
- 第 i 只奶牛参加会展：$dp[i][j]=dp[i−1][j−a[i].iq]+a[i].eq$
- 加上决策，选取上面两种情况的最大值：$dp[i][j]=max(dp[i−1][j],dp[i−1][j−a[i].iq]+a[i].eq)$
2.数字量偏移详解
dp[i] 表示「经过偏移处理后，下标为 i 时，对应的实际智商和为 i - tot，此时的最大情商和为 dp[i]」
这里的 tot 是偏移量（在代码中等于 n*1000），它的作用是将可能出现的负数智商和映射到数组的非负下标上。例如：
- 当实际智商和为 0 时，对应的数组下标是
tot（因为 0 + tot = tot）。
- 当实际智商和为 正数（如 5）时，对应的数组下标是
tot + 5。
- 当实际智商和为 负数（如 - 5）时，对应的数组下标是
tot - 5。
因为数组下标不能是负数，但我们需要处理智商和为负数的情况。通过引入 tot 作为偏移量：
i < tot 的部分：对应实际智商和为负数（例如 i = tot - 10 对应实际智商和为 -10）。i = tot 的部分：对应实际智商和为 0（初始状态）。i > tot 的部分：对应实际智商和为正数（例如 i = tot + 10 对应实际智商和为 +10）。
特别的：中间态实际上会出现一个花费背包空间为负的物品需要放入，此时会从比更大的背包转移，所以是正序遍历。需要注意的是：我们只对$j$这个变量做了偏移处理！
STD:
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
|
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N = 2e5+10;
struct node
{
int u,v;
};
node ipt[N];
int dp[N];
void solve()
{
int n;cin >> n;
for(int i=1;i<=n;i++) cin >> ipt[i].u >> ipt[i].v;
int tot = n*1000;
for(int i=0;i<=tot*2;i++) dp[i] = -1e8;
dp[tot] = 0;
for(int i=1;i<=n;i++)
{
if(ipt[i].u<0 and ipt[i].v<0) continue;
if(ipt[i].u<0)
{
for(int j=0;j<=tot*2+ipt[i].u;j++)
dp[j] = max(dp[j],dp[j-ipt[i].u]+ipt[i].v);
}
else
{
for(int j=tot*2;j>=ipt[i].u;j--)
dp[j] = max(dp[j],dp[j-ipt[i].u]+ipt[i].v);
}
}
int ans = -1;
for(int i=tot;i<=2*tot;i++)
{
if(dp[i]<0) continue;
ans = max(ans,dp[i]+i-tot);
}
cout << (ans==-1 ? 0 : ans) << endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int _ = 1;
//cin >> _;
while(_--)
{
solve();
}
return 0;
}
|
单调队列+01背包问题
思路：
1.dp的思路来源
我们发现，对于每个奶牛，我们要考虑选还是不选，于是有了第一种想法：
- 对于一头奶牛，如果我们不选，则有:$dp[i][0] = max(dp[i-1][0],dp[i-1][0])$
那考虑选这头奶牛：
从第一头奶牛开始看，我们发现到了第$k+1$头的时候，需要满足第二个条件，即不能连续的超过$k$头，如果我们要选择这头奶牛的话，意味着前面$k$头需要考虑一头不选，这头不选的设为$j,j\in(1\le j \le k)$，并且，如果我们不选$j$，那么在$j$到$i$之间会出现$[j+1,i-1]$是会被选择的，所以总的来看，对于第$k+1$头牛而言，选它的转移为
$$
dp[k+1][1] = max\{dp[j][0]+sum[k]-sum[j],j\in[1,k]\}
$$推广到任意一头牛，则有$j\in(i-k\le j \le i-1)$，那么需要找出这个区间中最大的那个$dp[j][0]$，那么转移方程为：
$$
dp[i][1] = max\{dp[j][0]-sum[j],j\in[i-k,i-1]\}+sum[i-1]
$$2.单调队列的思路来源
我们发现，对于第$i$头牛而言，总是需要维护一个最大值：
$$
mx = max\{dp[j][0]-sum[j],j\in[i-k,i-1]\}
$$于是考虑最大最小值动态维护的办法：单调队列+滑动窗口。
STD：
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
|
#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N = 2e5+10;
int n,k;
int pre[N];
int dp[N][2];
void solve()
{
cin >> n >> k;
for(int i=1;i<=n;i++)
{
int t;cin >> t;
pre[i] = pre[i-1] + t;
}
deque<int> dq;
dq.push_back(0);
for(int i=1;i<=n;i++)
{
dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
while(!dq.empty() and dq.front()<i-k) dq.pop_front();
dp[i][1] = dp[dq.front()][0] + pre[i] - pre[dq.front()];
while(!dq.empty() and dp[dq.back()][0] - pre[dq.back()] < dp[i][0] - pre[i]) dq.pop_back();
dq.push_back(i);
}
cout << max(dp[n][1],dp[n][0]) << endl;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int _ = 1;
//cin >> _;
while(_--)
{
solve();
}
return 0;
}
|
