傳送門(mén)

文章目錄

• 題意：
• 思路：

題意：

給你兩個(gè)長(zhǎng)度為$n$的數(shù)組$a,b$，你可以至多反轉(zhuǎn)一段連續(xù)區(qū)間，求${\sum }_{i=1}^n{a}_i?b_i$最大是多少。
$n<=5e3$

思路：

首先我們可以通過(guò)$n^2$來(lái)枚舉所有的區(qū)間，但是要計(jì)算翻轉(zhuǎn)之后的貢獻(xiàn)的話還需要多加一個(gè)$n$，這樣復(fù)雜度是$n^3$，顯然不可接受。
考慮能否通過(guò)小區(qū)間來(lái)遞推出大區(qū)間。
定義$f[i][j]$為將$[i,j]$段區(qū)間翻轉(zhuǎn)之后變換的值，我們發(fā)現(xiàn)如果我們知道一個(gè)小區(qū)間$[l,r]$，那么$[l?1,r+1]$的區(qū)間貢獻(xiàn)就是在$[l,r]$的貢獻(xiàn)基礎(chǔ)上再將$l?1,r+1$兩個(gè)位置的值互換了一下，互換兩個(gè)值$l,r$對(duì)答案的貢獻(xiàn)為$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])$，所以我們可以通過(guò)$[l,r]$擴(kuò)展到$[l?1,r+1]$，所以轉(zhuǎn)移方程為$$f[l][r]=f[l?1][r+1]+(a[l]?a[r])?(b[r]?b[l])$$
復(fù)雜度$O(N^2)$

#include<bits/stdc++.h> using namespace std;const int N=5010;typedef long long LL;int n; LL a[N],b[N]; LL f[N][N],pre[N];int main() {cin>>n;LL ans=0;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];for(int i=1;i<=n;i++) ans+=a[i]*b[i],pre[i]=ans;for(int len=2;len<=n;len++) {for(int l=1;l+len-1<=n;l++) {int r=l+len-1;f[l][r]=f[l+1][r-1]+(a[l]-a[r])*(b[r]-b[l]);ans=max(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])

總結(jié)

以上是生活随笔為你收集整理的Educational Codeforces Round 108 (Rated for Div. 2) D. Maximum Sum of Products 思维 + dp的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。