取数游戏2

1、原问题：每次能从a的左端或者右端取一个值和取b的最左值相乘后求总和

2、子问题（终态思考）： 最小区间取值都与b的最右端相乘后随着len的扩大b值逐渐向左取

3、状态参数：len(从1开始)，l，r

4、状态转移方程：

• dp[l][r] = max(dp[l][r] , dp[l][r-1]+a[r]*b[n-len+1]);
• dp[l][r] = max(dp[l][r] , dp[l+1][r]+a[l]*b[n-len+1]);

5、初始化：初始化dp都为0

6、是否优化：否

7、实现方式：逆向思维

8、答案位置：dp[1][n];

9、思考：为何无k值摆动求最大值？

• 因为该题不是无规律的求两块区间的值来比较大小，他是有规律的要么取左值，要么取右值。
• 主要的原题思想是：取了左值或者右值后，区间缩小一位，此时的要求情况是小一位的区间已经有了最优值，但是还没有
• 逆向思维（终态思考）：从最小区间（长度为1）开始去乘最右端的B，求值后取最优。然后逐渐扩大len范围，同时B值向左取

```int t，n;
void solve()
{
    cin>>n;
    vector<vector<int> > dp(1010,vector<int>(1010,0));
    vector<int>a(2*n+2);
    vector<int>b(2*n+2);
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> b[i];
    for(int len = 1; len <= n; ++len)
        for(int l = 1; l <= n-len +1; ++l)
        {
            int r = l + len -1;
            dp[l][r] = max(dp[l][r] , dp[l][r-1]+a[r]*b[n-len+1]);
            dp[l][r] = max(dp[l][r] , dp[l+1][r]+a[l]*b[n-len+1]);
        }
    cout<<dp[1][n]<<endl;
}
int main()
{
    cin >> t;
    while (t--)
    {
       solve();
    }
    return 0;
}