【经典dp】8.13序列

经典的拆绝对值

题目大意

给定$n$个具有顺序的序列，允许对每个序列循环移动。记第$i$个序列尾元素为$x$，$i+1$个序列首元素为$y$，定义其连接收益为$|x-y|*i$，求$n$个序列连接最大收益。

$\sum n \le 10^6$

题目分析

经典dp做得少

考虑如何处理绝对值：绝对值按分类讨论分开无非就两种情况$x*i-y*i$或者$y*i-x*i$，并且两者异号，相当于转为$\max$的问题。

因而不需要管两个元素的相对大小，只需要记录元素$a_v$的$\max\{f_{a_v}-a_v*i\}$和$\max\{f_{a_v}+a_v*i\}$.转移时候两者分开。

意会一下就是如下图

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 3 const ll INF = 1ll<<60;
 4 const int maxn = 1000035;
 5 
 6 int T,n,len[maxn],id[maxn];
 7 ll f[maxn],ans,pre,suf;
 8 std::vector<int> a[maxn];
 9 
10 int read()
11 {
12     char ch = getchar();
13     int num = 0, fl = 1;
14     for (; !isdigit(ch); ch=getchar())
15         if (ch==‘-‘) fl = -1;
16     for (; isdigit(ch); ch=getchar())
17         num = (num<<1)+(num<<3)+ch-48;
18     return num*fl;
19 }
20 int main()
21 {
22     for (T=read(); T; --T)
23     {
24         n = read(), id[0] = 1;
25         for (int i=1; i<=n; i++)
26         {
27             a[i].clear(), len[i] = read(), id[i] = id[i-1]+len[i-1];
28             for (int j=1; j<=len[i]; j++)
29                 a[i].push_back(read());
30         }
31         ans = pre = suf = 0;
32         for (int i=1; i<=n; i++)
33         {
34             ll nxtp = -INF, nxts = 0, val = 0;
35             for (int j=0,mx=a[i].size(),lst; j<mx; j++)
36             {
37                 lst = j?(j-1):a[i].size()-1;
38                 val = std::max(pre+1ll*a[i][j]*(i-1), suf-1ll*a[i][j]*(i-1));
39                 ans = std::max(ans, val);
40                 nxtp = std::max(nxtp, val-1ll*a[i][lst]*i);
41                 nxts = std::max(nxts, val+1ll*a[i][lst]*i);
42             }
43             pre = nxtp, suf = nxts;
44         }
45         printf("%lld\n",ans);
46     }
47     return 0;
48 }

END