如何用本地视频做网站,x浏览器,做网站最主要是那个一类商标,阿里云 多域名解析 到不同的网站传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你两个长度为nnn的数组a,ba,ba,b#xff0c;你可以至多反转一段连续区间#xff0c;求∑i1nai∗bi\sum _{i1}^n a_i*b_i∑i1nai∗bi最大是多少。 n5e3n5e3n5e3
思路#xff1a;
首…传送门
文章目录题意思路题意
给你两个长度为nnn的数组a,ba,ba,b你可以至多反转一段连续区间求∑i1nai∗bi\sum _{i1}^n a_i*b_i∑i1nai∗bi最大是多少。 n5e3n5e3n5e3
思路
首先我们可以通过n2n^2n2来枚举所有的区间但是要计算翻转之后的贡献的话还需要多加一个nnn这样复杂度是n3n^3n3显然不可接受。 考虑能否通过小区间来递推出大区间。 定义f[i][j]f[i][j]f[i][j]为将[i,j][i,j][i,j]段区间翻转之后变换的值我们发现如果我们知道一个小区间[l,r][l,r][l,r]那么[l−1,r1][l-1,r1][l−1,r1]的区间贡献就是在[l,r][l,r][l,r]的贡献基础上再将l−1,r1l-1,r1l−1,r1两个位置的值互换了一下互换两个值l,rl,rl,r对答案的贡献为a[l]∗b[l]a[r]∗b[r]a[l]∗b[r]a[r]∗b[l]a[l]∗(b[r]−b[l])a[r]∗(b[l]−b[r])a[l]*b[l]a[r]*b[r] a[l]*b[r]a[r]*b[l]a[l]*(b[r]-b[l])a[r]*(b[l]-b[r])a[l]∗b[l]a[r]∗b[r]a[l]∗b[r]a[r]∗b[l]a[l]∗(b[r]−b[l])a[r]∗(b[l]−b[r])所以我们可以通过[l,r][l,r][l,r]扩展到[l−1,r1][l-1,r1][l−1,r1]所以转移方程为f[l][r]f[l−1][r1](a[l]−a[r])∗(b[r]−b[l])f[l][r]f[l-1][r1](a[l]-a[r])*(b[r]-b[l])f[l][r]f[l−1][r1](a[l]−a[r])∗(b[r]−b[l]) 复杂度O(N2)O(N^2)O(N2)
#includebits/stdc.h
using namespace std;const int N5010;typedef long long LL;int n;
LL a[N],b[N];
LL f[N][N],pre[N];int main() {cinn;LL ans0;for(int i1;in;i) cina[i];for(int i1;in;i) cinb[i];for(int i1;in;i) ansa[i]*b[i],pre[i]ans;for(int len2;lenn;len) {for(int l1;llen-1n;l) {int rllen-1;f[l][r]f[l1][r-1](a[l]-a[r])*(b[r]-b[l]);ansmax(ans,f[l][r]pre[n]);}}printf(%lld\n,ans);return 0;
}//a[l]*b[l]a[r]*b[r] a[l]*b[r]a[r]*b[l]
//a[l]*(b[r]-b[l])a[r]*(b[l]-b[r])
