题解 P2426 【删数】

洛谷题目传送门

一眼看去：区间DP

数据范围：三重循环

好了不装B了，开始说正事

这题非常明显是区间DP。

按照惯例，先定义状态。

分析题目，发现除了区间左端点和右端点之外，什么也不需要加进状态里。因为显而易见除了区间左右端点，没有什么能够影响答案。

所以我们定义状态$dp[l][r]$为区间$[l,r]$的最大答案。

这个“操作价值”可以两重循环预处理出来，所以用$pre[l][r]$代表删除区间$[l,r]$的最大价值。非常明显的，甚至题目里已经直接写明白了，其实不用预处理，现场算就行，反正是$O(1)$的

\[pre[l][r]=
\begin{cases} a[l],
& \text {$l=r$} \\
|a[l]-a[r]|\times (r-l+1), & \text{$else$} \end{cases}
\]

然后就是最重要的一步——状态转移方程。

题目里有一个操作，就是一个区间删除一些数，失去一些“潜在的”价值。那么把这个过程反过来，一个区间加上一些数，得到一些“潜在的”价值。答案就是区间$[1,n]$的最大潜在价值。

可以得到：

\[dp[l][r]=\max_{i⊆[l,r-1]} \max (dp[l][i]+pre[i+1][r],pre[l][i]+dp[i+1][r])
\]

翻译成人话就是，一个区间的潜在价值，等于从左边删去一些数或者从右边删去一些数后再加上删去的数的价值的较大值。

知道了状态转移方程，代码就非常好写了。

AC Code:

#include <bits/stdc++.h> //赞美万能头！

using namespace std;

#define MAXN 105

int n,a[MAXN],dp[MAXN][MAXN],pre[MAXN][MAXN];

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        scanf("%d",&a[i]);

        pre[i][i]=dp[i][i]=a[i];//因为题目中的特殊约定“如果只去掉一个数，操作价值为这个数的值。”

    }

    for(int len=2;len<=n;len++){

        for(int l=1;l<=n-len+1;l++){

            int r=l+len-1;

            pre[l][r]=dp[l][r]=abs(a[l]-a[r])*(r-l+1);//预处理，因为有可能最优方案是把区间[l,r]都删掉，所以要给dp[l][r]也赋值。

        }

    }

    for(int len=2;len<=n;len++){

        for(int l=1;l<=n-len+1;l++){

            int r=l+len-1;

            for(int i=l;i<=r-1;i++){

                dp[l][r]=max(dp[l][r],dp[l][i]+pre[i+1][r]);

                dp[l][r]=max(dp[l][r],pre[l][i]+dp[i+1][r]);//就是状态转移方程233

            }

        }

    }

    printf("%d\n",dp[1][n]);//输出总的“潜在价值”。

    return 0;

}

由于LZ非常菜，有可能有自以为是的地方，所以请在评论区无情的指出qwq

巴特西

题解 P2426 【删数】

最新文章

热门文章