给定两个序列 a和 b ，将 a中的一个子序列翻转后 ( 也可以不翻转 ) ，使得 a，b 对应项乘积和最大。当时首先想到的是类似区间DP的东西，然后不知道怎么回事脑子晕了觉得枚举能做，枚举确实能做，但是又把数据范围搞错了，误以为要开高精度才行，然后搞了半天没时间了。
首先是枚举做法，这应该是比较经典的字符串枚举算法了。容易想到朴素的方法是枚举两个端点，将之间的部分进行翻转，但是这样复杂度过高。其实每次可以枚举翻转区间的中间点，然后很容易可以向两边扩展。设翻转区间的端点为u和v，则每次区间扩展对于扩展前区间的影响是a[v]*b[u]+a[u]*b[v]-a[u]*b[u]-a[v]*b[v].对于由于翻转区间的长度可能是奇数或者偶数，因此需要分两种情况。当然也可以通过中间补0的方式使之变成一种情况。
DP的做法大同小异，仍然是扩展区间，但是用了区间DP的思路。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #define LL long long 6 using namespace std; 7 const int N=5050<<1; 8 LL a[N],b[N]; 9 LL s; 10 int n; 11 int main(){ 12 13 cin>>n; 14 for(int i=1;i<=n*2;i+=2) cin>>a[i]; //n乘2因为中间要补0 15 for(int i=1;i<=n*2;i+=2) cin>>b[i]; 16 for(int i=1;i<=n*2;i++) s+=a[i]*b[i]; 17 LL maxx=0; 18 for(int i=1;i<=n*2;i++){ 19 LL p=0; 20 for(int l=i,r=i;l>=1 && r<=n*2;l--,r++){ 21 p+=(a[r]*b[l]+a[l]*b[r]-a[l]*b[l]-a[r]*b[r]); 22 maxx=max(maxx,p); 23 } 24 } 25 26 cout<<s+maxx; 27 28 return 0; 29 30 31 }
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 #define LL long long 6 using namespace std; 7 const int N=5050; 8 LL a[N],b[N]; 9 LL s; 10 int n; 11 LL f[N][N]; 12 int main(){ 13 14 cin>>n; 15 for(int i=1;i<=n;i++) cin>>a[i]; 16 for(int j=1;j<=n;j++) cin>>b[j]; 17 for(int i=1;i<=n;i++) s+=a[i]*b[i]; 18 19 for(int i=1;i<=n;i++) f[i][i]=s; 20 for(int len=2;len<=n;len++) 21 for(int l=1;l+len-1<=n;l++){ 22 int r=l+len-1; 23 if(len==2) f[l][r]=f[l][l]-a[l]*b[l]-a[r]*b[r]+a[l]*b[r]+a[r]*b[l]; //注意特殊处理一下len==2的情况 24 else f[l][r]=f[l+1][r-1]-a[l]*b[l]-a[r]*b[r]+a[l]*b[r]+a[r]*b[l]; 25 } 26 LL res=0; 27 for(int i=1;i<=n;i++) 28 for(int j=i;j<=n;j++) res=max(res,f[i][j]); 29 30 cout<<res; 31 32 return 0; 33 34 35 }
Educational Codeforces Round 108 (Rated for Div. 2) D. Maximum Sum of Products
原文：https://www.cnblogs.com/talk-sea/p/14728669.html