TopCoder SRM 353 Div1 Medium PlatformJumper

問題

n個の足場があり、それぞれの座標および、そこに置かれているコインの数が与えられる。
足場は点とみなす。

どれか好きな足場からスタートし、足場から足場へジャンプすることを繰り返してコインを集める。
ジャンプは、水平方向の速度がv以下で垂直方向の初速が0で、重力加速度gで落下する運動である。

集められるコインの枚数の最大値を求めよ。

制約条件

足場の数≦50
0≦X,Y≦5000
コインの数≦10000

方針

各足場から各足場へ移動できるかは、以下のように考える。
水平方向の移動距離をdx,垂直方向の落下距離をdyとして、
（まずdy＞0であることが必要）

速度vで飛び出したとき、t=dx/v秒後にx座標が次の足場のx座標になる。
この時間の間の落下距離gt^2/2が、dy以下ならば、その足場へ移動できる。

移動できるかの関係ができたら、グラフがDAGになるので、
適当にメモ化再帰して探索すればいい。

ソースコード

int n,can[50][50],c[50],dp[50];
int rec(int p){
	if(dp[p]>=0)return dp[p];
	dp[p]=0;
	rep(i,n)if(can[p][i]){
		dp[p]=max(dp[p],rec(i));
	}
	dp[p]+=c[p];
	return dp[p];
}
class PlatformJumper {
	public:
	int maxCoins(vector <string> platforms, int v, int g) 
	{
		vi x,y;
		n=platforms.size();
		rep(i,n){
			stringstream ss(platforms[i]);
			int p,q,r;
			ss>>p>>q>>r;
			x.pb(p); y.pb(q); c[i]=r;
		}
		memset(can,0,sizeof(can));
		rep(i,n)rep(j,n)if(y[i]>y[j]){
			int dx=abs(x[i]-x[j]), dy=y[i]-y[j];
			double t=dx*1.0/v;
			can[i][j]=g*t*t/2<dy+EPS;
		}
		//rep(i,n)rep(j,n)cerr<<can[i][j]<<(j==n-1?"\n":" ");
		memset(dp,-1,sizeof(dp));
		int ans=0;
		rep(i,n)ans=max(ans,rec(i));
		return ans;
	}
};