您的位置: 首页  >  IT文章  >  Codeforces Round #286 (Div. 二) C. Mr. Kitayuta, the Treasure Hunter

Codeforces Round #286 (Div. 二) C. Mr. Kitayuta, the Treasure Hunter

分类: IT文章 • 2024-05-16 21:39:43
Codeforces Round #286 (Div. 2) C. Mr. Kitayuta, the Treasure Hunter

C. Mr. Kitayuta, the Treasure Hunter
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The Shuseki Islands are an archipelago of 30001 small islands in the Yutampo Sea. The islands are evenly spaced along a line, numbered from 0 to 30000 from the west to the east. These islands are known to contain many treasures. There are n gems in the Shuseki Islands in total, and the i-th gem is located on island pi.

Mr. Kitayuta has just arrived at island 0. With his great jumping ability, he will repeatedly perform jumps between islands to the east according to the following process:

  • First, he will jump from island 0 to island d.
  • After that, he will continue jumping according to the following rule. Let l be the length of the previous jump, that is, if his previous jump was from island prev to island cur, let l = cur - prev. He will perform a jump of length l - 1, l or l + 1 to the east. That is, he will jump to island (cur + l - 1), (cur + l) or (cur + l + 1) (if they exist). The length of a jump must be positive, that is, he cannot perform a jump of length 0 when l = 1. If there is no valid destination, he will stop jumping.

Mr. Kitayuta will collect the gems on the islands visited during the process. Find the maximum number of gems that he can collect.

Input

The first line of the input contains two space-separated integers n and d (1 ≤ n, d ≤ 30000), denoting the number of the gems in the Shuseki Islands and the length of the Mr. Kitayuta's first jump, respectively.

The next n lines describe the location of the gems. The i-th of them (1 ≤ i ≤ n) contains a integer pi (d ≤ p1 ≤ p2 ≤ ... ≤ pn ≤ 30000), denoting the number of the island that contains the i-th gem.

Output

Print the maximum number of gems that Mr. Kitayuta can collect.

Sample test(s)
Input
4 10
10
21
27
27
Output
3
Input
8 8
9
19
28
36
45
55
66
78
Output
6
Input
13 7
8
8
9
16
17
17
18
21
23
24
24
26
30
Output
4
Note

In the first sample, the optimal route is 0  →  10 (+1 gem)  →  19  →  27 (+2 gems)  → ...

In the second sample, the optimal route is 0  →  8  →  15  →  21 →  28 (+1 gem)  →  36 (+1 gem)  →  45 (+1 gem)  →  55 (+1 gem)  →  66 (+1 gem)  →  78 (+1 gem)  → ...

In the third sample, the optimal route is 0  →  7  →  13  →  18 (+1 gem)  →  24 (+2 gems)  →  30 (+1 gem)  → ...

题意：0~30000有30001个地方，每个地方有一个或多个金币，第一步走到了d，步长为d，以后走的步长可以是上次步长+1,-1或不变，走到某个地方可以收集那个地方的财富，现在问走出去(>30000)之前最多可以收集到多少财富。

解法：容易想到DP，dp[i][j]表示到达 i 处，现在步长为 j 时最多收集到的财富，转移也不难,cnt[i]表示 i 处的财富。

dp[i+step-1] = max(dp[i+step-1],dp[i][j]+cnt[i+step+1])

dp[i+step] = max(dp[i+step],dp[i][j]+cnt[i+step])

dp[i+step+1] = max(dp[i+step+1],dp[i][j]+cnt[i+step+1])

但是步长直接开30000存的话肯定是不行的，又发现，其实走过30000之前，步长的变化不会很大，如果步长每次增加1的话，那么最少1+2+...+n=n(n+1)/2 > 30000, n<250，即步长变化不会超过250.所以第二维保存相对原始步长的改变量，-250~250，开500就够了，这样就不会MLE了。

#include<iostream>
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int dp[30010][510],p[30010],goal,d;
int dfs(int v,int l)
{
	if(v>=goal)
		return p[v];
	if(dp[v][l+250]!=-1)
		return dp[v][l+250];
	int to=d+l+v,mx=0;
	if(to-1>v&&to-1<=30000)
		mx=max(mx,dfs(to-1,l-1));
	if(to<=30000)
		mx=max(mx,dfs(to,l));
	if(to+1<=30000)
		mx=max(mx,dfs(to+1,l+1));
	dp[v][l+250]=p[v]+mx;
	return dp[v][l+250];
}
int main()
{
	int n;
	cin>>n>>d;
	while(n--)
	{
		int t;
		cin>>t;
		goal=max(t,goal);
		p[t]++;
	}
	memset(dp,-1,sizeof(dp));
	cout<<dfs(d,0);
}


相关推荐