题解 | 取数游戏

//  #牛客春招刷题训练营# https://www.nowcoder.com/discuss/726480854079250432
//  最近写的都是这种题，枚举len的dp
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define pre(i,j,k) for (int i = j; i < k; i++)
using namespace std;
int ans = 0;
int main() {
  ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  int n;
  cin >> n;
  vector<int> a(n);
  pre(i, 0, n) cin >> a[i];
  vector<int> b(n);
  pre(i, 0, n) cin >> b[i];
  vector<vector<int>> dp(n, vector<int>(n, 0));
  pre(len, 1, n + 1){
    pre(i, 0, n){
      int j = i + len - 1;
      if (j >= n) break;
      if (i == j) dp[i][j] = a[i] * b[n - 1];//--------ps：这里别写成len-1了，虽然也能过4组样例
      else{
        dp[i][j] = max(dp[i][j - 1] + a[j] * b[n - len], dp[i + 1][j] + a[i] * b[n - len]);
		//------推导我是反过来看的看成一次放一个只能放在队列的左右两边，虽然情况不完全一样
      }
    }
  }
  cout << dp[0][n - 1];
  return 0;
}
// 64 位输出请用 printf("%lld")