题解：CF358D Dima and Hares

· · 题解

CF358D Dima and Hares

零、废话

是不是考虑该降降难度了。

一、题意

自行理解。

二、思路

注意到第 i 个兔子产生的贡献和 i-1,i-2 的喂萝卜顺序有关，因此考虑延迟计算贡献的 dp。

定义 f_i 表示先喂 i-1 再喂 i 的最优结果。

定义 g_i 表示先喂 i 再喂 i-1 的最优结果。

:::info{open} 单独一个数无法看出相邻顺序，但用这两个状态，我们就可以表达三只相邻兔子的喂养顺序了。

而延迟计算 dp 就是在求解前 i 只兔子时，才去算第 i-1 只的贡献。（因为处理到 i 时，才刚好确定了 i-2,i-1,i 的顺序。）

边界 f_1=-\infty,g_1=0。

容易看出答案是 \max(f_n+b_n,g_n+a_n)。

转移式子也是顺水推舟地想出来了：

f_i=\max(f_{i-1}+b_{i-1},g_{i-1}+a_{i-1}) g_i=\max(f_{i-1}+c_{i-1},g_{i-1}+b_{i-1})

三、代码

#include<iostream>
#define int long long
using namespace std;
const int N = 3000;
int n;
int f[N+5],g[N+5];
int a[N+5],b[N+5],c[N+5];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<=n;i++) cin>>c[i];

    f[1] = -2e18;
    g[1] = 0;
    for(int i=2;i<=n;i++)
    {
        f[i] = max(f[i-1]+b[i-1],g[i-1]+a[i-1]);
        g[i] = max(f[i-1]+c[i-1],g[i-1]+b[i-1]);
    }

    cout<<max(f[n]+b[n],g[n]+a[n]);
    return 0;
}

四、总结 & trick

1. 延迟计算贡献 dp

因为正常的 dp 需要在当前状态的所有信息都确定后才能转移。而此题中，第 i 个兔子的贡献与它和 i+1 的顺序有关，因此你必须等到计算 i+1 的状态时，再回头结算 i 的贡献。

2. 闲话

不知道为什么这个题 n 只有 3000。

五、AI 使用声明

使用 Deepseek 改正错误 \LaTeX。