Kuangbin 线性DP 最大和加强加强版

ゝ一世哀愁。 2024-03-26 16:06 109阅读 0赞

**呃呃，一道题写了我一下午**

[4546. 最大和加强加强版 - AcWing题库][4546. _ - AcWing]

题意：

![ba4b2758a59b89b0eeb48789768a7b67.png][]

思路：

首先这道题没有明显的阶段，因此状态设计不能按照阶段去设计

我们按照题目给的量去设计状态：

设dp\[i\]\[j\]为考虑前i个数分为j组的最大可能和

如果这样设的话，我们去考虑转移，发现转移的过程中需要分类讨论，即对于最后一个数进行分类讨论

因此还要再加一维k，表示最后一个数是不是和前一个数是连着的

最后一个数：

一、单独作为一组：

然后考虑讨论前一个数的状态：

1.  前一个数作为单独一个组

1.  前一个数与前前的数作为一个组

二、和前一个数作为一组：

1.  前一个数和最后一个数作为一个组

1.  前一个数与前前数和最后一个数作为一个组

一、

1.  dp\[i\]\[j\]\[1\]=max(dp\[i\]\[j\]\[1\],dp\[i-1\]\[j-1\]\[0\])

1.  dp\[i\]\[j\]\[1\]=max(dp\[i\]\[j\]\[1\],dp\[i-1\]\[j-1\]\[1\])

二、

1.  dp\[i\]\[j\]\[1\]=max(dp\[i\]\[j\]\[1\],dp\[i-1\]\[j\]\[1\]+a\[i\])

dp\[i\]\[j\]\[0\]=max(dp\[i\]\[j\]\[0\],max(dp\[i-1\]\[j-1\]\[0\],dp\[i-1\]\[j-1\]\[1\]))

Code：

#include <bits/stdc++.h>
    #include <cmath>
    //#define int long long
    using namespace std;
    using i64 = long long;
    const int mxn=1e3+10;
    const int mxe=1e6+10;
    
    int n,m;
    int a[mxe];
    i64 dp[2][mxn][2];
    void solve(){
        while(cin>>m>>n){
            for(int i=1;i<=n;i++) cin>>a[i];
            memset(dp,-0x3f,sizeof(dp));
            dp[0&1][0][0]=0;
            for(int i=1;i<=n;i++){
                dp[i&1][0][0]=0;
                for(int j=1;j<=m;j++){
                    //第i个数作为单独一组：
                    dp[i&1][j][1]=max(dp[(i-1)&1][j-1][0],dp[(i-1)&1][j-1][1])+a[i];
                    //第i个数不作为单独一组：
                    dp[i&1][j][1]=max(dp[i&1][j][1],dp[(i-1)&1][j][1]+a[i]);
                    dp[i&1][j][0]=max(dp[(i-1)&1][j][0],dp[(i-1)&1][j][1]);
                }
            }
            cout<<max(dp[n&1][m][0],dp[n&1][m][1])<<'\n';
        }
    }
    void init(){}
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        init();
        while(__--)solve();return 0;
    }

[4546. _ - AcWing]: https://www.acwing.com/problem/content/4549/
[ba4b2758a59b89b0eeb48789768a7b67.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/420a776d41a848dea5c2ea3cbe40028a.png