AcWing,第108场周赛T3
前置知识：P1115 最大子段和 的dp和线段树作法
分析：对于一个数组，可以直接求出最大字段和，但由于多个数组拼接在一起，没有办法直接求得拼接数组的最大字段和。求最大字段和我已知有两种方法：
- dp
- 线段树
先对每一个数组用线段树求出最大前缀和，最大字段和，最大后缀和，再才用Dp的思路求出拼接后数组的最大字段和，和P1115 最大子段和 的dp作法差不多
\[res = \max (seg_{b_{i}ms}, dp_{i - 1} + seg_{b_{i}ls},dp_{i - 1} + seg_{b_{i}s}, seg_{b_{i}rs}) \\ dp_i = \max (dp_{i - 1} + seg_{b_{i}s}, seg_{b_{i}rs},0) \]\(i\) 代表拼接数组的第 \(i\) 个数组，\(\texttt{seg}\) 代表线段树处理的最大前缀和，最大字段和，最大后缀和，数组值分别为\(\texttt{ls,ms,rs,s}\) ， \(b_i\) 是要拼接的数组
// AC one more times
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 3e5 + 10;
int n, m, a[60][5010], l[N];
ll f[N];
struct info
{
ll ms,ls,rs,s;
};
info operator + (const info t1,const info t2)
{
info t;
t.s=t1.s+t2.s;
t.ls=max(t1.ls,t1.s+t2.ls);
t.rs=max(t2.rs,t2.s+t1.rs);
t.ms=max({t.ls,t.rs,t1.ms,t2.ms,t1.rs+t2.ls});
return t;
}
struct segtree
{
info t;
}seg[60][N];
void update(int x, int id)
{
seg[x][id].t=seg[x][id*2].t+seg[x][id*2+1].t;
}
void buildtree(int x, int id,int l,int r)
{
if(l==r)
{
seg[x][id].t={a[x][l],a[x][l],a[x][l],a[x][l]};
return;
}
int mid=(l+r)>>1;
buildtree(x, id*2,l,mid);
buildtree(x, id*2+1,mid+1,r);
update(x, id);
}
void solve()
{
cin>>n>>m;
for(int i = 1; i <= n; i++)
{
cin>>l[i];
for(int j = 1; j <= l[i]; j++)
cin>>a[i][j];
buildtree(i, 1, 1, l[i]);
}
ll res = -(1ll << 60ll);
for(int i = 1; i <= m; i++)
{
int id; cin>>id;
res = max({res, seg[id][1].t.ls + f[i - 1], seg[id][1].t.ms, f[i - 1] + seg[id][1].t.s, seg[id][1].t.rs});
f[i] = max({f[i - 1] + seg[id][1].t.s, seg[id][1].t.rs, 0ll});
}
cout<<res<<'\n';
return;
}
int main()
{
std::ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int TC = 1;
//cin >> TC;
for(int tc = 1; tc <= TC; tc++)
{
//cout << "Case #" << tc << ": ";
solve();
}
return 0;
}