CF1472C Long Jumps题解

【题目分析】

本题有两个方法，

方法一：每一个位置可得的分分别求出，打擂找出最大（可得部分分）

方法二：从后往前求可得的分数，以避免一些不必要的重复。

【设计程序】

方法一：

#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<queue>
using namespace std;
const int N = 2 * 1e5 + 5;
int a[N];
int n;
long long score(int x)//求这个位置出发可得的分
{
	long long ans = 0;
	while(x <= n)//当x还在n的范围中时
	{
		ans += a[x];//加这个位置的值
		x += a[x];//把x标到下一个位置
	}
	return ans;//返回得分
}
int main()
{
	int p;
	scanf ("%d", &p);//输入组数
	while (p--)
	{
		long long maxn = 0;
		scanf ("%d", &n);//输入数据个数
		for (int i = 1;i <= n; i++)//输入数据
			scanf ("%d", a + i);
		for (int i = 1;i <= n; i++)//从每一个位置开始
			maxn = max(maxn, score(i));//求最大值
		printf ("%d\n", maxn);//输出最大值
	}
	return 0;
}

方法二：

#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<queue>
using namespace std;
const int N = 2 * 1e5 + 5;
int a[N];
long long b[N];//b[i]表示从i出发可得的分数
int n;
int main()
{
	int p;
	scanf ("%d", &p); //输入组数
	while (p--)
	{
		scanf ("%d", &n); //输入数据个数
		for (int i = 1;i <= n; i++)//输入数据
			scanf ("%d", a + i);
		for (int i = n;i >= 1; i--)
		{
			if (i + a[i] > n)
			//如果后一个位置在n的范围外
				b[i] = a[i];//此位置的得分为本位置的值
			else//如果在n中
				b[i] = a[i] + b[i + a[i]];
				//本位置的值加上下个位置的得分
		}
		long long maxn = b[1];
		for (int i = 2;i <= n; i++)//打擂找最大
			maxn = max(maxn, b[i]);
		printf ("%d\n", maxn);//输出最大值
	}
	return 0;
}

【调试代码】

1. 测试样例
2. 自测数据（特殊值，边界值）

数据：

4

5

0 0 0 0 0

3

3 2 1

1

1000

5

1 1 1 1 1