首页 > 代码库 > Codeforces 75D Big Maximum Sum 最大子段和 dp
Codeforces 75D Big Maximum Sum 最大子段和 dp
题目链接:点击打开链接
题意:
第一行 n m
n个vector
下面n行 第一个数字u表示vector 的大小,然后后面u个数字给出这个vector
最后一行m个数字
表示把上面的vector拼接起来
得到一个大序列,求这个大序列的最大子段和
先预处理出每个vector的最大子段和,左起连续最大,右起连续最大,所有数的和
然后dp 一下。。
#include <cstdio> #include <iostream> #include <algorithm> #include <string.h> #include <vector> using namespace std; const long long inf = 1e18; #define ll long long #define N 250010 inline ll Max(ll n, ll x[]){ ll ans = x[0], sum = x[0]; for(ll i = 1; i < n; i++) { sum += x[i]; ans = max(ans, sum); } return ans; } vector<ll>G[N]; ll n, m; ll l[N],r[N],cop[N],sum[N], w[N]; ll work(ll x){ ll ans = G[x][0], sum = 0; for(ll i = 0; i < G[x].size(); i++) { if(sum + G[x][i] >= 0){ sum += G[x][i]; ans = max(ans, sum); } else sum = 0; ans = max(ans, G[x][i]); } return ans; } void input(){ for(ll i = 1; i <= n; i++){ G[i].clear(); sum[i] = 0; ll u, v; scanf("%I64d",&u); while(u--) { scanf("%I64d",&v); G[i].push_back(v); sum[i] += v; } for(ll j = 0; j < G[i].size(); j++)cop[j] = G[i][j]; l[i] = Max((ll)G[i].size(), cop); for(ll j = 0; j < G[i].size(); j++)cop[G[i].size()-j-1] = G[i][j]; r[i] = Max((ll)G[i].size(), cop); w[i] = work(i); } } ll dp[250010][2]; int main() { ll u; while(~scanf("%I64d %I64d",&n,&m)) { input(); ll ans = -inf; dp[0][0] = dp[0][1] = -inf; for(ll i = 1; i <= m; i++) { scanf("%I64d", &u); dp[i][0] = dp[i-1][1] + max(sum[u], l[u]); dp[i][0] = max(dp[i][0], max(sum[u], l[u])); dp[i][1] = dp[i-1][1] + sum[u]; dp[i][1] = max(dp[i][1], sum[u]); dp[i][1] = max(dp[i][1], r[u]); ans = max(ans, dp[i][0]); ans = max(ans, dp[i][1]); ans = max(ans, w[u]); } cout<<ans<<endl; } return 0; } /* 3 4 8 -10 1 9 9 -10 2 -10 -9 7 3 -10 -10 -6 3 -7 0 1 -3 1 3 2 3 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。