Monday, January 19, 2015

Codeforces Round #286 (Div. 1 A / Div. 2 C) - Mr. Kitayuta, the Treasure Hunter

Problem Statement:
506A - Mr. Kitayuta, the Treasure Hunter

Solution:
This is a standard dynamic programming problem, with a non-standard twist!

Firstly, let's forget about the constraints, define M(i, len) be the maximum number of gems can be collected if we start from island i after making a jump of length len. This is simply M(i, len) = max of  {M(i+len-1, len-1), M(i+len, len), M(i+len+1, len+1)} + [whether there is a gem in island i or not]. But we have a problem: Doing this will take $$O(N^2)$$ where $$N \leq 30000$$, which will not going to cut it in 1 second time constraint.

So the main observation is to realize that we don't require that much states after all, since in the worst case, len can only range from [1 .. 300], so there are less than 600 possible values for len in any case, reducing the runtime complexity to $$O(NM)$$ where $$M < 600$$.

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <utility>
#include <string>
using namespace std;

int dp[603][30003];
int mark[30003];
int N, D;
int Z = 299;
int main(){
int u;
scanf("%d %d",&N,&D);
for(int i=0;i<N;++i){
scanf("%d",&u);
mark[u]++;
}
for(int i=30000;i>=0;--i){
for(int k=0;k<=600;++k){
dp[k][i] = mark[i];
int cur = D+k-Z;
if(cur<1)continue;
if(i+cur<=30000){
dp[k][i] = max(dp[k][i],dp[k][i+cur]+mark[i]);
}
if(i+cur+1<=30000 && k!=600){
dp[k][i] = max(dp[k][i],dp[k+1][i+cur+1]+mark[i]);
}
if(i+cur-1<=30000 && cur != 1){
dp[k][i] = max(dp[k][i],dp[k-1][i+cur-1]+mark[i]);
}
}
}
printf("%d\n",dp[Z][D]);
return 0;
}