题解 | 取数游戏

取数游戏

https://www.nowcoder.com/practice/b467563ebc14407d842f0bb4680f52d8

//  #牛客春招刷题训练营# 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")

#牛客春招刷题训练营##写题解领奖励#
全部评论

相关推荐

07-17 11:27
门头沟学院 Java
点赞 评论 收藏
分享
06-28 22:48
已编辑
广东金融学院 Java
小浪_Coding:学院本+这俩项目不是buff叠满了嘛
点赞 评论 收藏
分享
07-09 20:50
门头沟学院 Java
码农索隆:1.教育背景和荣誉证书合二为一。 2.获奖项目理一遍,你做了什么,对你求职的岗位有什么帮助,没有就删掉。 3.技能特长和教育背景交换位置。 4.技能特长写的太差,上网上找简历参考。都不用问你别的,一个redis就能把你问住,写写你具体会redis哪些方面的知识。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务