取数游戏

Love The Way You Lie 2022-06-03 10:26 193阅读 0赞

*  题目描述:
    
    > 给定两个长度为n的整数列A和B，每次你可以从A数列的左端或右端取走一个数。假设第i次取走的数为ax，则第i次取走的数的价值vi=bi⋅ax，现在希望你求出∑vi的最大值。
 *  输入描述：
    
    > 第一行一个数T，表示有T组数据。  
    > 对于每组数据，第一行一个整数n，  
    > 接下来两行分别给出A数列与B数列。
 *  输出描述：
    
    > 每一组数据输出一行，最大的∑vi。
 *  示例：  
    
    
     *  输入
    
    > 2  
    > 2  
    > 1 1000  
    > 2 1  
    > 5  
    > 1 3 5 2 4  
    > 1 2 3 4 5
 *  输出
    
    > 2001  
    > 52
 *  说明  
    
    
    > 对于第二个样例，  
    > 第一次从左边取走a1，v1=a1⋅b1=1,  
    > 第二次从左边取走a2，v2=a2⋅b2=6,  
    > 第三次从右边取走a5，v3=a5⋅b3=12,  
    > 第四次从右边取走a4，v4=a4⋅b4=8,  
    > 第五次取走剩下的a3，v5=a3⋅b5=25。  
    > 总价值∑vi=1+6+12+8+25=52

*  备注：
    
    > T≤10  
    > 1≤n≤103  
    > 1≤ai,bi≤103
 *  程序代码：(搜索)
    
        #include<iostream>
         #include<cstring>
         #include<algorithm>
         #include<set>
         #define N 1200
        using namespace std;
         int a[N];
                int b[N];
                int dp[N][N];
        int dfs(int l,int r,int t){
              if(l>r)  return 0;
              if(dp[l][r]) return dp[l][r];
              int temp=0;
              temp=max(temp,dfs(l,r-1,t+1)+a[r]*b[t]);
              temp=max(temp,dfs(l+1,r,t+1)+a[l]*b[t]);
        return dp[l][r]=temp;
        
        }
        int main(){
            int t;
            cin>>t;
            while(t--){
               memset(dp,0,sizeof(dp));
                int m;
                cin>>m;
                for(int i=0;i<m;i++)cin>>a[i];
                for(int i=0;i<m;i++)cin>>b[i];
                cout<<dfs(0,m-1,0)<<endl;
            }
           return 0;
        }