P2627 和 P2340 两道DP
Link:Luogu
P2627 [USACO11OPEN] Mowing the Lawn G
题目描述
在一年前赢得了小镇的最佳草坪比赛后，Farmer John 变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，Farmer John 希望能够再次夺冠。
然而，Farmer John 的草坪非常脏乱，因此，Farmer John 只能够让他的奶牛来完成这项工作。Farmer John 有 $N$（$1\le N\le 10^5$）只排成一排的奶牛，编号为 $1ldots N$。每只奶牛的效率是不同的，奶牛 $i$ 的效率为 $E_i$（$0\le E_i\le 10^9$）。
靠近的奶牛们很熟悉，因此，如果 Farmer John 安排超过 $K$ 只连续的奶牛，那么，这些奶牛就会罢工去开派对 :-)。因此，现在 Farmer John 需要你的帮助，计算 FJ 可以得到的最大效率，并且该方案中没有连续的超过 $K$ 只奶牛。
输入格式
- 第一行：空格隔开的两个整数 $N$ 和 $K$。
- 第二到 $N+1$ 行：第 $i+1$ 行有一个整数 $E_i$。
输出格式
- 第一行：一个值，表示 Farmer John 可以得到的最大的效率值。
输入输出样例 #1
输入 #1
1
2
3
4
5
6
5 2
1
2
3
4
5
输出 #1
1
12
解析
我们直观分析，很明显能发现这是一个线性DP题目，因为对于每个奶牛我们有两个选项——选与不选(0/1)。
转移方程
由此我们可以得到转移表达式：
$dp[i][0] = \max(dp[i - 1][0], dp[i - 1][0]) $ $dp[i][1] = \max(dp[j][0] - sum[j] + sum[i]),(i - k \le j \le i)$
先好好思考一下第二个转移公式，第二个公式的含义是在节点 $i$ 不选节点 $j$ 时的在最大值，此时的 $j$ 是枚举出来的
优化
分析第二个公式，发现：
- $sum[i]$ 是不会随着 $j$ 而发生变化的 于是方程可以转化为：$dp[i][1] = max(dp[j][0] - sum[j]) + sum[i],(i - k \le j \le i)$
- 我们始终是在寻找 $dp[j][0] - sum[j]$ 在区间 $i - k \le j < i$ 的最大值，我们就能使用单调队列使其递减
进一步地，我们能把转移方程优化为一维DP：
\[dp[i]=\max \left\{ \begin{array}{l} dp[i - 1] \\ \max (dp[j - 1] - sum[j]) + sum[i], (i - k \le j \le i) \end{array} \right.\]核心代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int a[N], s[N], f[N];
int d[N], q[N], head = 0, tail = 1;
// 此处 d 为值表，q 为队列
void solve()
{
int n, k; cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i], s[i] = s[i - 1] + a[i];
for (int i = 1; i <= n; i++)
{
d[i] = f[i - 1] - s[i];
// 更新值表
while (head <= tail && d[q[tail]] < d[i]) tail--;
q[++tail] = i;
while (head <= tail && q[head] < i - k) head++;
// 更新单调队列
f[i] = d[q[head]] + s[i];
// 转移方程
}
cout << f[n] << endl;
}
Link:Luogu
P2340 [USACO03FALL] Cow Exhibition G
题目描述
奶牛想证明它们是聪明而风趣的。为此，贝西筹备了一个奶牛博览会，她已经对 $N$ 头奶牛进行了面试，确定了每头奶牛的智商和情商。
贝西有权选择让哪些奶牛参加展览。由于负的智商或情商会造成负面效果，所以贝西不希望出展奶牛的智商之和小于零，或情商之和小于零。满足这两个条件下，她希望出展奶牛的智商与情商之和越大越好，请帮助贝西求出这个最大值。
输入格式
第一行：单个整数 $N$，$1 \le N \le 400$。
第二行到第 $N+1$ 行：第 $i+1$ 行有两个整数：$S_i$ 和 $F_i$，表示第 $i$ 头奶牛的智商和情商，$-1000 \le S_i;F_i \le 1000$。
输出格式
输出单个整数：表示情商与智商和的最大值。贝西可以不让任何奶牛参加展览，如果这样做是最好的，输出 $0$。
输入输出样例 #1
输入 #1
1
2
3
4
5
6
5
-5 7
8 -6
6 -3
2 1
-8 -5
输出 #1
1
8
说明/提示
选择第一头，第三头，第四头奶牛，智商和为−5+6+2 = 3，情商和为7−3+1 = 5。再加入第二号奶牛可使总和提升到10，不过由于情商和变成负的了，所以是不允许的
解析
这个题同样也是一道DP题，但是没有连续性的限制，因此是一道01背包题 我们这里把体积看成奶牛的智商，背包容量看成奶牛的个数，价值看成奶牛的情商。 此时的 $dp[i][j]$ 表示前 $i$ 只奶牛中，总智商为 $j$ 时情商的最大值.
转移方程
此时的状态转移方程为
\[dp[i][j]=\max \left\{ \begin{array}{l} dp[i−1][j] \text{，第 i 只奶牛不参加会展} \\ dp[i - 1][j - a[i].iq] + a[i].eq \text{，第 i 只奶牛参加会展} \end{array} \right.\]优化
- 很明显，我们开二维数组会
MLE，故我们要压缩到一维DPEQ 和 IQ 的范围为 $(-4e5~4e5)$
此时的转移方程为
\[dp[j]=\max \left\{ \begin{array}{l} dp[j] \text{，第 i 只奶牛不参加会展} \\ dp[j - a[i].iq] + a[i].eq, \text{，第 i 只奶牛参加会展} \end{array} \right.\] - 但是有些奶牛会有负智商，我们就需要正着DP，否则我们在处理dp的时候可能会重复计数同一个奶牛
- 但是还有一个问题，就是智商和可能为负，我们就需要将dp数组右移
核心代码
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
int dp[2*N + 5];
void solve()
{
int n; cin >> n;
fill(dp, dp + 2 * N + 5, -inf);
dp[N] = 0;
for (int i = 0; i < n; i++)
{
int s, f; cin >> s >> f;
if (s >= 0)
{
for (int p = N * 2 - s; p >= 0; p--)
{
if (dp[p] != -inf)
{
dp[p + s] = max(dp[p + s], dp[p] + f);
}
}
}
else
{
for (int p = -s; p <= N * 2; p++)
{
if (dp[p] != -inf)
{
dp[p + s] = max(dp[p + s], dp[p] + f);
}
}
}
}
int ans = 0;
for (int s = 0; s <= N; s++)
{
int f = dp[s + N];
if (f >= 0) ans = max(ans, f + s);
}
cout << ans << endl;
}