CF75D Big Maximum Sum 题解

chenzhiyv · 2025-04-11 17:08:07 · 题解

CF75D Big Maximum Sum

具体思路

首先，我们考虑大数组的答案构成是什么，经过思考，可以得出只有两种情况：

1. 是某个小数组的最大子段和。
2. 跨越了很多个小数组。

这样我们就可以设出 O(n^2) 的 dp：

设 dp[i][j] 表示以大数组的第 i 位结尾，结尾是第 i 个小数组的第 j 位的最大子段和，转移为：

这里的 maxsum[i][j] 表示第 i 个小数组以第 j 位结尾的最大子段和， big[i] 表示大数组第 i 位的值， siz[i] 表示第 i 个小数组的长度， presum[i][j] 表示第 i 个小数组的前 j 位的前缀和。

然后，我们发现这个转移我们只用到了 dp[i-1] 的最后一项，也就是全选的情况，这时我们考虑将这个数单独存下，来优化时间复杂度。

设 dp[i][0/1] 表示以大数组的第 i 位结尾，可能不全选小数组/全选小数组中的数的最大子段和。

转移：

这里 premax[i] 表示第 i 个小数组的前缀最大值， sufmax[i] 是后缀最大值， sum[i] 是和， maxsum[i] 最大子段和。

答案就是所有的值的最大值。

代码（加入滚动数组优化）：

#include<bits/stdc++.h>
namespace fast_IO {
#define IOSIZE 1000000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
using namespace std;
#define int long long
const int N=50+10,M=2.5e5+10,L=5e3+10;
int n,m;
int siz[N];
int small[L];
int pre_sum[N];
int suf_max[N];
int dp_s[2];
int max_sum[N];
int pre_max[N];
int big[M];
int dp[2][2];
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>siz[i];
        for(int j=1;j<=siz[i];j++)
        {
            cin>>small[j];
            pre_sum[i]=pre_sum[i]+small[j];
            pre_max[i]=max(pre_sum[i],pre_max[i]);
        }
        suf_max[i]=-1e9;
        int suf_sum=0;
        for(int j=siz[i];j>=1;j--)
        {
            suf_sum=suf_sum+small[j];
            suf_max[i]=max(suf_sum,suf_max[i]);
        }
        dp_s[0]=dp_s[1]=-1e9;
        max_sum[i]=pre_max[i]-1e9;
        for(int j=1,o=1;j<=siz[i];j++,o^=1)
        {
            dp_s[o]=max(dp_s[o^1]+small[j],small[j]);
            max_sum[i]=max(max_sum[i],dp_s[o]);
        }
    }
    for(int i=1;i<=m;i++)
        cin>>big[i];
    dp[0][0]=dp[0][1]=dp[1][0]=dp[1][1]=-1e9;
    int ans=-1e9;
    for(int i=1,o=1;i<=m;i++,o^=1)
    {
        dp[o][0]=max(dp[o^1][1]+pre_max[big[i]],max_sum[big[i]]);
        dp[o][1]=max(dp[o^1][1]+pre_sum[big[i]],suf_max[big[i]]);
        ans=max({ans,dp[o][0],dp[o][1]});
    }
    cout<<ans;
    return 0;
}