题面

有两个长为

n 的序列

a 和

b，至多反转

a 的一个子区间，最大化

∑

⋅

\sum_{i=1}^na_i\cdot b_i

∑i=1nai⋅bi 并输出这个值。

≤

5000

1\leq n\leq5000

1≤n≤5000，答案不会爆 long long。

题解

绝大部分人都在考场上用的是官方题解的做法，基本没有什么别的做法了，如果有，那估计就是提交榜单最末尾那些1900+ ms的做法吧。

数据非常小，再加上又是Div2，让人不禁想起暴力做法。朴素的暴力是枚举要翻转的区间

[

]

[l,r]

[l,r] ，然后把它带给答案的变化量加上，取最优输出。

这样是

(

)

O(n^3)

O(n3) 的，过不了。为什么这个暴力不可行，因为我们每次计算区间

[

]

[l,r]

[l,r] ，都要把整个

[

]

[l,r]

[l,r] 模拟翻转一遍在计算答案，这是低效的。

只要我们注意到

[

]

[l,r]

[l,r] 的答案可以从

[

−

]

[l+1,r-1]

[l+1,r−1] 的答案

(

)

O(1)

O(1) 转移过来，我们就解决这个问题了。这很好理解，因为这两个区间的旋转中心相等，它们的模拟翻转过程只有最边上不同。

你可以暴力从每个旋转中心往外扩展计算，也可以用 Dynamic Programming 仿照上面说的转移写。都是

(

)

O(n^2)

O(n2) 的，差别不大。

CODE

#include<set>

#include<queue>

#include<cmath>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 5005

#define ENDL putchar('\n')

#define LL long long

#define DB double

#define lowbit(x) ((-x) & (x))

LL read() {

	LL f = 1,x = 0;char s = getchar();

	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}

	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}

	return f * x;

}

int n,m,i,j,s,o,k;

LL a[MAXN],b[MAXN];

int main() {

	n = read();

	LL sum = 0;

	for(int i = 1;i <= n;i ++) a[i] = read();

	for(int i = 1;i <= n;i ++) {

		b[i] = read(); sum += a[i] * b[i];

	}

	LL ans = sum;

	for(int i = 1;i <= n;i ++) {// 从中心扩展

		LL sm = sum;

		for(int j = i-1,k = i+1;j > 0 && k <= n;j --,k ++) { // 长度为奇数，中心是个点

			sm -= a[j]*b[j] + a[k]*b[k];

			sm += a[j]*b[k] + a[k]*b[j];

			ans = max(ans,sm);

		}

		sm = sum;

		for(int j = i,k = i+1;j > 0 && k <= n;j --,k ++) { // 长度为偶数，中心是个分界线

			sm -= a[j]*b[j] + a[k]*b[k];

			sm += a[j]*b[k] + a[k]*b[j];

			ans = max(ans,sm);

		}

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

[CF1519D] Maximum Sum of Products （暴力）

题面

题解

CODE

最新文章

热门文章