官方题解 | 加固

这道题得90分的同学大多就是因为没有特判n = 1 的情况，这次也算是提醒了大家看测试点数据的重要性了。

下面给出 $2$ 种对于这道题的解法：

$A$：三维动态规划

在这个问题中，我们需要最大化在森林环形结构中小猪家园存活后保留的金币总数。由于家园是环形的，每个小猪有两个邻居，强化一个小猪的家会从其两个邻居那里各拿走 c 个金币。我们的目标是决定哪些小猪的家应该被强化，使得在攻击后幸存的家园中的金币总数最大.

为了解决这个问题，我们可以使用动态规划（DP）。我们需要记录到当前小猪为止，考虑强化或不强化当前小猪时，能够获得的最大金币数。由于问题涉及环形结构，我们可以将其转化为线性问题，通过两次DP处理来解决.

动态规划状态定义

我们使用三维数组 dp[i][j][k] 来表示状态，其中：

• i 表示当前考虑到第 i 只小猪.
• j 表示第 i-1 只小猪是否被强化（0 表示未强化，1 表示强化）.
• k 表示第 i 只小猪是否被强化（0 表示未强化，1 表示强化）.

状态转移方程

• 如果第 i 只小猪不强化 (k = 0)：
  • 如果第 i-1 只小猪强化 (j = 1)：dp[i][0][0] = max(dp[i-1][1][0], dp[i-1][1][1] - 2*c)
  • 如果第 i-1 只小猪不强化 (j = 0)：dp[i][0][0] = max(dp[i-1][0][0], dp[i-1][0][1])
  • 加上第 i 只小猪的初始金币：dp[i][0][0] += a[i]
• 如果第 i 只小猪强化（k = 1）：
  • 如果第 i-1 只小猪强化 (j = 1)：dp[i][1][0] = max(dp[i-1][1][0] - 2*c, dp[i-1][0][0]) - 2*c
  • 如果第 i-1 只小猪不强化 (j = 0)：dp[i][1][0] = max(dp[i-1][0][0], dp[i-1][0][1]) - 2*c
  • 加上第 i 只小猪的初始金币：dp[i][1][0] += a[i]

注意：这里的 dp[i][1][0] 应该是 dp[i][1][1]，因为我们在考虑第 i 只小猪强化的情况.

修正后的状态转移方程为：

• dp[i][0][0] = max(dp[i-1][1][0], dp[i-1][0][0]) + a[i]
• dp[i][0][1] = max(dp[i-1][1][1] - 2*c, dp[i-1][0][1]) + a[i]
• dp[i][1][0] = max(dp[i-1][1][0] - 2*c, dp[i-1][0][0]) - 2*c + a[i] (这种情况实际不会用到，因为 k 表示当前小猪的强化状态)
• dp[i][1][1] = max(dp[i-1][1][1] - 2*c, dp[i-1][0][1]) - 2*c + a[i]

由于我们只关心最后一只小猪之前的状态，并且我们最终需要的结果是在第 n 只小猪考虑强化或不强化时的最大值，所以最终答案应该从 dp[n][0][0], dp[n][0][1], dp[n][1][0] (这里实际上不需要考虑，因为最终小猪不能单独强化而不考虑最后一个邻居), dp[n][1][1] - 2*c (如果第 n 只小猪强化，并且考虑从第 1 只小猪不再拿走金币的情况) 中选取.

边界条件

• 初始化 dp[1][...] 时，由于第 0 只小猪不存在（环形结构），我们需要单独处理第一只小猪的情况.

#include<bits/stdc++.h>
using namespace std;
long long a[200010],n,c;
long long dp[200010][2][2];
int main(){
    cin >> n >> c;
    for(long long i = 1;i <= n;i++) cin >> a[i];
    dp[1][1][1] = a[1];
    dp[1][0][1] = dp[1][1][0] = -0x3f3f3f3f;
    dp[1][0][0] = 0;
    for(long long i = 2;i <= n;i++){
        dp[i][0][0] = max(dp[i - 1][1][0],dp[i - 1][0][0]);
        dp[i][0][1] = max(dp[i - 1][1][1],dp[i - 1][0][1]);
        dp[i][1][0] = max(dp[i - 1][1][0] - 2 * c,dp[i - 1][0][0]) + a[i];
        dp[i][1][1] = max(dp[i - 1][1][1] - 2 * c,dp[i - 1][0][1]) + a[i];
    }
    long long ans = 0;
    ans = max(ans,max(dp[n][0][1],dp[n][0][0]));
    ans = max(ans,dp[n][1][0]);
    ans = max(ans,dp[n][1][1] - 2 * c);
    cout << ans;
    return 0;
}

时间复杂度：$O(N)$.

---

$B$：二维动态规划

这种解法是我通过观察Macw老师的代码想到的（真是太妙啦！）.

在这个问题中，我们需要最大化在森林环形结构中小猪家园存活后保留的金币总数。由于家园是环形的，每个小猪有两个邻居，且强化一个小猪的家会从其两个邻居那里各拿走 m 个金币（题目中的 c 在此解答中用 m 表示，以与代码一致）。我们的目标是决定哪些小猪的家应该被强化，使得在攻击后幸存的家园中的金币总数最大。

由于问题涉及环形结构，直接应用动态规划（DP）会比较复杂。为了简化问题，我们可以将环形结构拆分为两个线性问题：

1. Case A：假设不强化第1只小猪的家园。
2. Case B：假设强化第1只小猪的家园。

对于每种情况，我们可以使用动态规划来计算到第 n 只小猪时能够获得的最大金币数。

动态规划状态定义

我们使用二维数组 dp[i][j] 来表示状态，其中：

• i 表示当前考虑到第 i 只小猪。
• j 表示第 i 只小猪是否被强化（0 表示未强化，1 表示强化）。

状态转移方程

• 如果第i只小猪不强化 (j = 0)：
  • dp[i][0] = max(dp[i-1][0], dp[i-1][1])
• 如果第i只小猪强化 (j = 1)：
  • dp[i][1] = max(dp[i-1][0] + a[i], dp[i-1][1] + a[i] - 2*m)

其中，a[i] 表示第 i 只小猪家里初始的金币数。

边界条件

• 对于Case A：
  • dp[1][0] = 0（不强化第1只小猪）
  • dp[1][1] = -∞（禁用强化第1只小猪的情况）
• 对于Case B：
  • dp[1][0] = -∞（禁用不强化第1只小猪的情况）
  • dp[1][1] = a[1]（强化第1只小猪）

考虑环形特性

在 Case B 中，由于我们假设强化了第1只小猪，当计算到第 n 只小猪时，还需要考虑从第 n 只小猪到第1只小猪的额外金币扣除（因为它们是邻居）。但由于我们是线性处理，这个额外的扣除已经在 dp[n][1] 的计算中隐含处理了（即如果第 n 只小猪也强化，那么从 dp[n-1][1] 到 dp[n][1] 的转移已经扣除了 2m）。因此，在最终比较 Case A 和 Case B 的结果时，不需要再额外处理环形特性。

#include <bits/stdc++.h>
using namespace std;

static const long long NEG_INF = - (1LL << 60);

long long solveCaseA(int n, long long m, const vector<long long> &a)
{
    // Case A：固定“不选 1 号”
    // dp[i][0] = 考虑到第 i 只小猪，且第 i 只不加固时的最大收益
    // dp[i][1] = 考虑到第 i 只小猪，且第 i 只被加固时的最大收益

    vector<vector<long long>> dp(n+1, vector<long long>(2, NEG_INF));
    // 不选 1 号
    dp[1][0] = 0;      // 不加固 1 号
    dp[1][1] = NEG_INF; // “加固 1 号”这条路径在 Case A 里直接禁用

    for (int i = 2; i <= n; i++)
    {
        // i 不加固
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]);

        // i 被加固
        // 若 i-1 不加固
        long long candidate1 = dp[i-1][0] + a[i];
        // 若 i-1 也加固，则要多扣 2m
        long long candidate2 = dp[i-1][1] + a[i] - 2LL*m;
        dp[i][1] = max(candidate1, candidate2);
    }

    // 返回末尾的最大值
    return max(dp[n][0], dp[n][1]);
}

long long solveCaseB(int n, long long m, const vector<long long> &a)
{
    // Case B：固定“选了 1 号”
    // 同样的 DP 定义
    vector<vector<long long>> dp(n+1, vector<long long>(2, NEG_INF));

    // 1 号被加固
    dp[1][0] = NEG_INF; 
    dp[1][1] = a[1];   // 选了 1 号，收益为 a[1]

    for (int i = 2; i <= n; i++)
    {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
        long long candidate1 = dp[i-1][0] + a[i];
        long long candidate2 = dp[i-1][1] + a[i] - 2LL*m;
        dp[i][1] = max(candidate1, candidate2);
    }

    // 若第 n 号也加固，则因为它与 1 号相邻，多扣 2m
    // 因此要取 max(dp[n][0], dp[n][1] - 2m)
    long long ansWhenNChosen = dp[n][1] - 2LL*m;
    return max(dp[n][0], ansWhenNChosen);
}

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

    int n;
    long long m;
    cin >> n >> m;


    // 小猪的编号从 1 到 n，为了方便和上面 DP 的下标对应
    vector<long long> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }

    // 分两种情况
    if(n == 1){
        cout << 0 << endl;
        return 0;
    }

    long long ansA = solveCaseA(n, m, a);
    long long ansB = solveCaseB(n, m, a);
    cout << max(ansA, ansB) << "\n";
    
    return 0;
}

时间复杂度：$O(N)$.