D. Maximum Sum of Products

题目传送门

题目大意：

给两个字符a,b，在a中选一段连续子串，将其倒置（可以不选），计算ai*bi之和的最大值。

思路：

先计算前缀和，然后区间dp，枚举区间长度len，然后枚举左端点l，确定右端点r，将区间内的a倒置，判断区间内的值与未倒置之前的(s[r]-s[l-1])值差，取max，如果max大于0，则答案为s[n]+max,否则答案为s[n];

状态转移方程：

f[l][r]=f[l+1][r-1]+左端点+右端点

• 注意f[i][j]表示的是将区间内倒置的值，计算左端点和右端点的时候需要注意。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5005;
#define pii pair<int,int>
#define endl "\n"
#define ll long long
#define inf 0x3f3f3f3f
ll f[maxn][maxn];
ll s[maxn], a[maxn],b[maxn];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    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++)
        s[i] = s[i - 1] + a[i] * b[i];
    for (int i = 1; i <= n; i++) f[i][i] = a[i] * b[i]; 
    // 为什么这样初始化呢，因为中间的值不会改变，比如
    //f[1][3]=f[2][2]+左+右
    ll gap = 0;
    for (int len = 2; len <= n; len++)
    {
        for (int i = 1; i+len-1<=n; i++)
        {
            int l = i, r = i + len - 1;
            int temp = l + r;
            f[l][r]= f[l+1][r-1]+a[l] * b[temp-l] + b[temp-r] * a[r];
            gap = max(gap,f[l][r] - s[r] + s[l - 1]);
        }
    }
    if (gap > 0) cout << s[n] + gap << endl;
    else cout << s[n]<<endl;
    return 0;
}