牛客手速月赛40 B(怎么有人区间dp都不会啊?指自己)

题目

题意: 给定n个数，环形排列。任选一个起点，进行n次跳跃。只能选择相邻左边或者右边且没有跳过的位置进行跳跃，获得收益i * a[p]，i为第几次跳跃。求最大收益

思路: 纯纯的区间dp，数组扩展一倍即可。 定义f[l][r]表示区间[l,r]的最大收益 //f[l][r] = f[l+1][r] + a[l] * (r-l+1) 跳a[l] //f[l][r] = f[l][r-1] + a[r] * (r-l+1) 跳a[r] 记忆化搜索会好写一点，高中爷tql.

// Problem: 跳跳跳
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11217/B
// Memory Limit: 524288 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i