跳跳跳

NC227595. 跳跳跳

描述

$dd$ 在玩跳格子游戏，具体游戏规则如下，

$n$ 个格子呈环形分布，顺时针方向分别标号为 $1\sim n$ ，其中 $1$ 和 $n$ 相邻，每个格子上都有一个正整数 $a[i]$ ，玩家可以选择一个点作为起点开始跳 $n$ 下，第 $i$ 次跳跃，玩家只可以选择当前位置左边或右边最近且尚未被跳跃过的位置进行一次跳跃，并获得 $i\times a[p]$ 的得分，其中 $p$ 为第 $i$ 次跳跃的位置。

$dd$ 很鸡贼，想赢又不想动脑子，她希望你能给她规划路线以确保她的胜利

输入描述

第一行一个数n(1≤n≤2000)
接下来一行n个数，表示a[i](1≤a[i]≤2000)

输出描述

一个数，表示dd可能获得的最高分

示例1

输入:

3
1 1 1

输出:

说明:

可能方案
1->2->3
1->3->2
2->1->3
2->3->1
3->1->2
3->2->1
(以上数字表示格子标号)

答案均为 1*1+2*1+3*1=6

最优方案不唯一，最优答案唯一

示例2

输入:

3
1 2 3

输出:

说明:

方案:1->2->3（数字对应格子标号）

答案:1*1+2*2+3*3=14

最优方案唯一

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 34ms, 内存消耗: 23704K, 提交时间: 2021-11-05 20:16:17

#include<bits/stdc++.h>
using namespace std;
int n,a[4005],dp[2002][4002],ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)	scanf("%d",&a[i]),a[i+n]=a[i];
	for(int i=1;i<=n;i++)
	for(int j=1;i+j<=2*n;j++)
	{
		dp[i][j]=max(dp[i][j],max(dp[i-1][j]+i*a[i+j-1],dp[i-1][j+1]+i*a[j]));
	}
	for(int i=1;i<=n;i++)
	ans=max(ans,dp[n][i]);
	cout<<ans;
	return 0;
}

上一题

下一题

详情