G7022 [GESP202606 七级] 消消乐 题解

知识点：区间动态规划、最后操作、边界状态。

解题思路

区间DP枚举最后删去的元素k。删完左右子区间后，它的邻居固定为区间外的a[l-1]与a[r+1]，故转移为dp[l][k-1]+dp[k+1][r]+这两个边界值。

为什么正确

确定最后删除者后，左右子问题互不干扰且共享尚未删除的边界；枚举最后者覆盖全部删除次序。

易错点

两端补0；得分来自相邻元素之和，不是相乘，也不包含被删元素自身。

复杂度

时间O(n³)，空间O(n²)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<long long>a(n+2);
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<vector<long long>>dp(n+2,vector<long long>(n+2));
    for(int len=1;len<=n;len++)for(int l=1;l+len-1<=n;l++) {
        int r=l+len-1;
        for(int k=l;k<=r;k++)dp[l][r]=max(dp[l][r],dp[l][k-1]+dp[k+1][r]+a[l-1]+a[r+1]);
    }
    cout<<dp[1][n];
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。