• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

Educational Codeforces Round 108 (Rated for Div. 2) D. Maximum Sum of Products (区间dp)

开发技术 开发技术 6天前 7次浏览

Educational Codeforces Round 108 (Rated for Div. 2) D. Maximum Sum of Products (区间dp)

  • 题意:有两个长度为(n)的数组(a)(b),你可以对(a)的子数组反转一次,问你(sum_{i=1}^{n}a_i*b_i)的最大值.

  • 题解:一眼区间dp的题目,对于长度为(len)的子区间([l,r]),它可以从([l+1,r-1])转移过来,那么我们设(dp[i][j])为子区间([i,j])能得到的最大贡献,转移方程就为:(dp[i][j]=dp[i+1][j-1]+a[i]*b[j]+a[j]*b[i]).每次用当前区间的(dp)再加上左边和右边的前缀更新答案即可.

  • 代码:

    #include <bits/stdc++.h>
    #define ll long long
    #define fi first
    #define se second
    #define pb push_back
    #define me memset
    #define rep(a,b,c) for(int a=b;a<=c;++a)
    #define per(a,b,c) for(int a=b;a>=c;--a)
    const int N = 5005 ;
    const int mod = 1e9 + 7;
    const int INF = 0x3f3f3f3f;
    using namespace std;
    typedef pair<int,int> PII;
    typedef pair<ll,ll> PLL;
    ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
    ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
     
    int n;
    ll a[N];
    ll b[N];
    ll dp[N][N];
    ll pre[N];
     
    int main() {
        ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    	cin>>n;
    	rep(i,1,n) cin>>a[i];
    	rep(i,1,n) cin>>b[i];
    	ll res=0;
    	rep(i,1,n){
    		res+=a[i]*b[i];
    		dp[i][i]=a[i]*b[i];
    	}
     
    	rep(i,1,n){
    		pre[i]=pre[i-1]+a[i]*b[i];
    	}
    	
    	ll ans=pre[n];
    	for(int len=1;len<n;++len){
    		for(int i=1;i+len<=n;++i){
    			int j=i+len;
    			dp[i][j]=a[i]*b[j]+a[j]*b[i]+dp[i+1][j-1];
    			ans=max(ans,pre[i-1]+dp[i][j]+pre[n]-pre[j]);
    		}
    	}
     
    	cout<<ans<<'n';
     
        return 0;
    }
    

喜欢 (0)