魔法祭坛

对于20%的数据,我们只需要枚举左端点以及右端点O(n^2),通过前缀和维护答案(不熟悉前缀和的同学建议先去了解一下)。

通过观察数据范围可以发现a[i]的取值非常的小 , 我们尝试分析公式

$ ans(l, r) = (s[r] - s[l - 1]) - |a[l] - a[r]| * (r - l + 1) $

将 $|a[l] - a[r] |$ 看做是差值 d

则式子视作 $ans(l,r) = (s[r] - s[l - 1 ]) - (r - l + 1) * d = s[r] - r * d - d + l * d - s[ l - 1 ]$

我们可以按顺序枚举 r 端点 , 此时我们仍然有未知数d 但是 a[r]是已知的 , 我们可以直接枚举d , 或者是 a[l]

那我们选择枚举 a[l] (取值 - 100 ~ 100 ) 那这样 d 也就是已知常量 对于上述式子中未知的项剩下 l * d 与 - s[l - 1 ]

我们想让 ans(l ,r ) 最大 ，通过枚举 除了 l * d 与 s[l - 1 ] 是未知的 其他的值均已固定 所以我们需要找到某个端点 l 使得 l * d - s[l - 1 ] 的值最大 。 为了解决这个问题 ，我们定义数组 st [i] [j] 左端点的魔力值为 i 与右端点差值为 j 的最大值 我们可以在循环的结尾维护这个数组(因为是按顺序枚举的 r , 在该循环结束后 对于后面的 r 来说 当前端点就成为了 l ) 。

#include <iostream> 
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 3e5 + 10 , M = 500  ; 
int n ;
int a[N] , s[N] , st[M][M] ; 


int main()
{
    cin >> n ; 
    for(int i = 1;  i <= n ; i ++ ) 
        cin >> a[i] , s[i] = s[i - 1 ] + a[i] ; 
    
    memset(st , -0x3f , sizeof st ) ;    
    int ans = -1e9 ; 
    for(int i = 1 ; i <= n ; i ++ ) 
    {
        for(int c = - 100 ; c <= 100 ; c ++ ) //常数 c 
        {
            int d = abs(a[i] - c ) ; // i 作为 r  
            int cur = s[i] - i * d - d + st[c + 100][d] ;   
            if(cur > ans ) ans = cur ; 
        }
        for(int d = 0 ; d <= 200 ; d ++ ) 
        {// i 作为 l 
            st[a[i] + 100 ][d] = max(st[a[i] + 100 ][d] , i * d - s[i - 1 ] ) ; 
        }
    }
    
    cout << ans << endl ; 
    
    return 0 ; 
}

时间复杂度 : O(n * m ) , m <= 200

本题数据加强过，不建议使用map及哈希表（Py中的字典）。