【Kuangbin区间DP】奶牛零食

冷不防 2024-03-30 13:55 63阅读 0赞

[4558. 奶牛零食 - AcWing题库][4558. _ - AcWing]

题意：

![cadefdcf77fb447eacd00cc53e2bfe02.png][]

写了Kuangbin的三道DP，三道都不会QwQ

是不是该remake了....

思路：

一开始我天真的以为那个题单全是线性DP，然后我就自然而然往线性DP的方向上想了呜呜

我设 dp\[i\]\[j\]表示阶段 i ，且这个阶段 去掉的数为 j 的最大收益

然后我是这样转移的：

因为第 i 个阶段，我们去枚举状态

这个位置 j 一定在 \[1,i\] U \[n-i+1,n\]里面

dp\[i\]\[j\]=dp\[i-1\]\[j-1\]+i\*a\[j\] j属于\[1,i\]

dp\[i\]\[j\]=dp\[i-1\]\[j+1\]+i\*a\[j\] j属于\[n-i+1,n\]

写完还觉得这样非常的对，其实阶段就有问题啊

区间DP的阶段是以区间作为阶段的，而线性DP的阶段是以线性为阶段的

这道题，我们发现一个区间的子问题一定是它的子区间，那肯定是区间DP

然后状态转移就比较易错了

拿掉a\[l\]之前的收益是该轮的收益+区间\[l+1\]\[r\]的收益

拿掉a\[r\]之前的收益是该轮的收益+区间\[l\]\[r-1\]的收益

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=2e3+10;
    int n;
    int a[mxn],dp[mxn][mxn];
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int len=1;len<=n;len++){
            for(int l=1;l+len-1<=n;l++){
                int r=l+len-1;
                dp[l][r]=max(dp[l+1][r]+a[l]*(n-(r-l)),dp[l][r-1]+a[r]*(n-(r-l)));
            }
        }
        cout<<dp[1][n]<<'\n';
    }

**总结：**

**需要有点辨识度吧，以区间为状态那肯定是区间DP**

**然后写状态转移方程的时候，一定要按照定义来写，不然很容易写寄**

[4558. _ - AcWing]: https://www.acwing.com/problem/content/4561/
[cadefdcf77fb447eacd00cc53e2bfe02.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/62fa8bd288224c20a095239ea200f2a1.png