题解 | #取数游戏2#

学到动态规划学到后面反而忘了他最重要的本质， 动态规划的本质是一个状态和一个状态之间的转换。

本来开了个三维数组dp[i][j][k],代表的是从左拿了个，从右拿了j个，现在是第几个，其实简化后就成了dp[i][j]。

代码中的实现在两层循环可以实现，第一层枚举现在一共选了n个数，然后第二层枚举从左取了x个数，然后每一层的的状态就是dp[i][n-i](三个循环是整不过的）

```#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[1100],b[1100];
ll ans[1100][1100];
int t,n;
int main(){
        cin>>t;
    while(t--){
        cin>>n;
        for(int i=1; i<=n; i++)
            cin>>a[i];
        for(int i=1; i<=n; i++)
            cin>>b[i];
    
        int x;
        for(int bi=1; bi<=n; bi++){
            for(int i=0; i<=bi; i++){
                
                x=bi-i;
                    if(x==0)
                    {ans[i][x]=ans[i-1][x]+b[bi]*a[i]; continue;}
                    
                    if(i==0)
                    {ans[i][x]=ans[i][x-1]+b[bi]*a[n-x+1]; continue;}
                    
                    ans[i][x]=max(ans[i-1][x]+b[bi]*a[i],ans[i][x-1]+b[bi]*a[n-x+1]);
                
            }
        }
    
        ll maxn=0;
        for(int i=0; i<=n; i++)
            maxn=max(maxn,ans[i][n-i]);
        cout<<maxn<<"\n";
    }
    return 0;
}