取数游戏2

这个题做的时候发生了一个很搞笑的事情，就是如果你把代码里面的

int a[1011],b[1011];
int dp[1011][1011];

调换一下位置，哈，你就会惊喜的发现，段错误。
仅限c++11
题解：dp[i][j]代表着左边取i个数右边取j个数能获得的最大值。
当i+j==n的时候，就可以获得最大值了。
递推式：dp[i][j]=max(dp[i-1][j]+a[i]* b[i+j],dp[i][j-1]+a[n-j+1]*b[i+j]);

/*Keep on going Never give up*/
#include<bits/stdc++.h>
using namespace std;

int a[1011],b[1011];
int dp[1011][1011];

int main()
{
    int t;
    cin>>t;
    while(t--){
        int n;
        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][0]=dp[i-1][0]+a[i]*b[i];
            dp[0][i]=dp[0][i-1]+a[n-i+1]*b[i];
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=max(dp[i-1][j]+a[i]*b[i+j],dp[i][j-1]+a[n-j+1]*b[i+j]);
                if(i+j==n) ans=max(ans,dp[i][j]);
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}