题目描述:
给定两个长度为n的整数列A和B,每次你可以从A数列的左端或右端取走一个数。假设第i次取走的数为ax,则第i次取走的数的价值vi=bi⋅ax,现在希望你求出∑vi的最大值。
思路与分析:
我们定义它在区间[l,r]之间的最大值为dp[l][r]。
而dp[l][r]的值是由max(dfs(l+1,r,i+1)+b[i]a[l],dfs(l,r-1,i+1)+b[i]a[r])得来的。
所以我们可以的到dfs的代码
int dfs(int l,int r,int i) { if(i==n+1)return 0; if(dp[l][r]!=0)return dp[l][r]; return dp[l][r]=max(dfs(l+1,r,i+1)+b[i]*a[l],dfs(l,r-1,i+1)+b[i]*a[r]); }
由此代码我们便可推得它的递推式
dp[j][j+i]=max(dp[j+1][j+i]+a[j]*b[n-i],dp[j][j+i-1]+a[j+i]*b[n-i]);
AC代码如下:
#include<bits/stdc++.h> #define ll long long using namespace std; const ll N=1e3+10; ll a[N],b[N],dp[N][N]; int n; int main() { int t; cin>>t; while(t--) { cin>>n; memset(dp,0,sizeof(dp)); 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++)dp[i][i]=a[i]*b[n]; for(int i=1;i<n;i++) for(int j=1;j+i<=n;j++) dp[j][j+i]=max(dp[j+1][j+i]+a[j]*b[n-i],dp[j][j+i-1]+a[j+i]*b[n-i]); cout<<dp[1][n]<<'\n'; } return 0; }
另外此题也能用记忆化搜索做
#include<bits/stdc++.h> #define ll long long using namespace std; const ll N=1e3+10; ll a[N],b[N],dp[N][N]; int n; int dfs(int,int,int); int main() { int t; cin>>t; while(t--) { cin>>n; memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)cin>>b[i]; cout<<dfs(1,n,1)<<'\n'; } return 0; } int dfs(int l,int r,int i) { if(i==n+1)return 0; if(dp[l][r]!=0)return dp[l][r]; return dp[l][r]=max(dfs(l+1,r,i+1)+b[i]*a[l],dfs(l,r-1,i+1)+b[i]*a[r]); }