★问题描述
小 G 参加了一场游戏，游戏中有 20001 个格子（编号为 0~20000），小 G 初始时在编
号为 0 的格子上。小 G 可以按照以下规则在格子上移动。
1、 开始时，小 G 从编号为 0 的格子上移动到编号为 d 的格子上
2、 用 L 来表示上一次移动的距离,假设上一次移动中小 G 从编号 pre 的格子移动到编号
为 cur 的格子，则 L=pre-cur。下一次移动中小 G 只能向前移动 L-1， L， L+1 步，即小 G 只
能到达编号为（ cur+L-1）、（ cur+L）、（ cur+L+1）的格子。因为小 G 只能向前走不能停
留，所以当 L=1 时，只能移动 1 步或者 2 步，不能移动 0 步。
3、 当不存在可到达的格子时，游戏结束。
有的格子上会有一些宝石，小 G 站在编号为 i 的格子上时，则可以获得该格子上的宝石。
小 G 想知道游戏结束时，他最多可以获得多少宝石，请你帮助他。
★数据输入
输入的第一行为包括两个整数 n,d(1≤ n≤ 20000;1≤ d≤ 300)表示有 n 个格子上存在
宝石，第一次移动是从 0 移动到 d。
接 下 来 n 行 ， 每 行 包 括 一 个 整 数 。 第 i(1 ≤ i ≤ n) 行 的 数
pi (d ≤ p1 ≤ p2 ≤ ... ≤ pn ≤ 20000)表示编号为 pi 的格子上存在 1 个宝石。
30%的数据 n<=100。
70%的数据 n<=1000。
100%的数据 n<=20000.
解法：
容易想到DP，dp[i][j]表示到达 i 处，现在步长为 j 时最多收集到的财富，转移也不难,,cnt[i]表示 i 处的财富。
但由于n太大，用n*n的时间内存是不可以接受的
步长直接开20000存的话肯定是不行的，发现其实走过20000之前，步长的变化不会很大
若每一步以d+1的步长走，到达20000这个位置，则总的步长为：d+1+d+2+d+3+.......+d+n>=1+2+3+.....+n=n·(n+1)/2>=20000 解得n<=200
即步长变化不会超过200.所以第二维保存相对原始步长的改变量，-200~200，开400就够了，这样就不会MLE了。
求以d为起点的最优路径，应该从后往前dp。
dp[i][j]表示到达 i 处，先前的步长变化为j时最多收集到的财富。
步长变化：j
步长：L=d+j
从后往前dp如下 ：
dp[i][j]=0当i大于n（总格子的编号）
dp[i][j]=i格获得的宝石+max(dp[i+L][j],dp[i+L+1][j+1]) 当j==1&&i<=n
dp[i][j]=i格获得的宝石+max(dp[i+L][j],dp[i+L+1][j+1],dp[i+L-1][j-1]) 当j>1&&i<=n
步长的变化加一个偏移量：offset=200
dp[i][j+offset]=0当i大于n（总格子的编号）
dp[i][j+offset]=i格获得的宝石+max(dp[i+L][j+offset],dp[i+L+1][j+1+offset]) 当j==1&&i<=n
dp[i][j+offset]=i格获得的宝石+max(dp[i+L][j+offset],dp[i+L+1][j+1+offset],dp[i+L-1][j-1+offset]) 当j>1&&i<=n
解法二：
题意：0~30000有30001个地方，每个地方有一个或多个金币，第一步走到了d，步长为d，以后走的步长可以是上次步长+1,-1或不变，走到某个地方可以收集那个地方的财富，现在问走出去(>30000)之前最多可以收集到多少财富。
解法：容易想到DP，dp[i][j]表示到达 i 处，步长变化为 j 时最多收集到的财富，转移也不难,a[i]表示 i 处的财富。
step=d+j
dp[i+step-1][j-1]= max(dp[i+step-1][j-1],dp[i][j]+a[i+step+1])
dp[i+step][j] = max(dp[i+step][j],dp[i][j]+a[i+step])
dp[i+step+1][j+1] = max(dp[i+step+1][j+1],dp[i][j]+a[i+step+1])
j加了一个偏移量：step=d+j-250
步长直接开20000存的话肯定是不行的，发现其实走过20000之前，步长的变化不会很大
若每一步以d+1的步长走，到达20000这个位置，则总的步长为：d+1+d+2+d+3+.......+d+n>=1+2+3+.....+n=n·(n+1)/2>=20000 解得n<=200
即步长变化不会超过200.所以第二维保存相对原始步长的改变量，-200~200，开400就够了，这样就不会MLE了。
#include<stdio.h> #include<string.h> int num[30001],dp[30001][1001]; int max(int a,int b){return a>b?a:b;} int main(){ int n,d,x,i,j,ans; scanf("%d %d",&n,&d); for(i=0;i<n;i++) scanf("%d",&x),num[x]++; memset(dp,-1,sizeof(dp)); dp[d][500]=num[d];//初始化 ans=0; for(i=d;i<=30000;i++){ for(j=0;j<=1000;j++){//带偏移的步长变化 if(dp[i][j]==-1) continue;//判断第i个格子能否可达,如果可达,才可以往后跳 ans=max(ans,dp[i][j]); int L=d+j-500;//实际步长 if(L-1>0&&i+L-1<=30000)//不能移动0步 dp[i+L-1][j-1]=max(dp[i+L-1][j-1],dp[i][j]+num[i+L-1]); if(i+L<=30000) dp[i+L][j]=max(dp[i+L][j],dp[i][j]+num[i+L]); if(i+L+1<=30000) dp[i+L+1][j+1]=max(dp[i+L+1][j+1],dp[i][j]+num[i+L+1]); } } printf("%d\n",ans); return 0; }
/* dp[i][j]表示到达i处,步长为j时最多收集到的财富,a[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]) */ #include<stdio.h> #include<string.h> int n,d; int a[61000],f[61000][802]; int max(int a,int b){ return a>b?a:b; } int main(){ int k,i,j,t; scanf("%d %d",&n,&d); for (i=1;i<=n;i++){ scanf("%d",&t); a[t]++; } for (i=30000;i>=0;i--){ for (j=1;j<=800;j++){ k=j+d-400; if (k==1) f[i][j]=max(f[i+1][j]+a[i+1],f[i+1][j+1]+a[i+1]); if (k>1) f[i][j]=max(max(f[i+k][j-1]+a[i+k],f[i+k][j+1]+a[i+k]),f[i+k][j]+a[i+k]); } } printf("%d",f[0][400]); return 0; }
#include<stdio.h> #include<string.h> int b[30005][1100]; int a[30005]; int n,d,maxn; int max(int a,int b){ return a>b?a:b; } int dp(int i,int j){ int k; k=j-d+500; if(i>maxn) return 0; else if(j==0) return 0; else if(b[i][k]>=0) return b[i][k]; else return b[i][k]=max(max(dp(i+j+1,j+1),dp(i+j,j)),dp(i+j-1,j-1))+a[i]; } int main(){ maxn=0; scanf("%d %d",&n,&d); memset(a,0,sizeof(a)); memset(b,-1,sizeof(b)); for(int i=0;i<n;i++){ int t; scanf("%d",&t); if(maxn<t) maxn=t;//结束的位置 a[t]++;//这个岛的宝石数量， } printf("%d\n",dp(d,d)); return 0; }
http://www.icekrn.com/?p=609
京公网安备 11010502036488号