問題
http://community.topcoder.com/stat?c=problem_statement&pm=7847&rd=10710
x,y座標上に複数のプラットフォームがあり、各プラットフォームには任意の数のコインが存在する。
また、走る速さvと重力加速度gが与えられ、時間tあたりt*t*g/2の速さで落下していく。
プレイヤーは、走る速さvが足りていれば高いプラットフォームから低いプラットフォームへ移動することができる。
任意のプラットフォームからスタートできるとき、得られる最大のコインを求める。
解き方
ｄｐで解ける問題。
あるプラットフォームiに対して、そこから到達できる全てのプラットフォームのdp[j]のうち最大の値とプラットフォームiにあるコインの数の和がdp[i]になる。
届くか届かないかの判定の関数は、式を変形することでできるだけ割り算を少なくすることが誤差を小さくするポイント。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dp[60],n,v,g;
vector<pair<pair<int,int>,int> > p;
class PlatformJumper {
public:
int f(int pos){
if(dp[pos]!=-1)return dp[pos];
if(pos==n)return 0;
int x=p[pos].first.second,y=p[pos].first.first,score=p[pos].second;
int ret=score;
FORE(i,0,pos){
int tx=p[i].first.second,ty=p[i].first.first;
if(ty<y&&canjump(x,y,tx,ty))ret=max(ret,dp[i]+score);
}
return dp[pos]=ret;
}
bool canjump(int x1,int y1,int x2,int y2){
return abs(x1-x2)*abs(x1-x2)*(double)g<=abs(y1-y2)*2.0*v*v ? true :false;
}
int maxCoins(vector<string> platforms, int v_, int g_) {
n=platforms.size();
v=v_,g=g_;
memset(dp,-1,sizeof(dp));
p.clear();
FORE(i,0,n){
stringstream out(platforms[i]);
int t[3];
out>>t[0]>>t[1]>>t[2];
p.push_back(make_pair(make_pair(t[1],t[0]),t[2]));
}
sort(all(p));
int ret=0;
FORE(i,0,n)ret=max(ret,f(i));
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
int dp[60],n,v,g;
vector<pair<pair<int,int>,int> > p;
class PlatformJumper {
public:
int f(int pos){
if(dp[pos]!=-1)return dp[pos];
if(pos==n)return 0;
int x=p[pos].first.second,y=p[pos].first.first,score=p[pos].second;
int ret=score;
FORE(i,0,pos){
int tx=p[i].first.second,ty=p[i].first.first;
if(ty<y&&canjump(x,y,tx,ty))ret=max(ret,dp[i]+score);
}
return dp[pos]=ret;
}
bool canjump(int x1,int y1,int x2,int y2){
return abs(x1-x2)*abs(x1-x2)*(double)g<=abs(y1-y2)*2.0*v*v ? true :false;
}
int maxCoins(vector<string> platforms, int v_, int g_) {
n=platforms.size();
v=v_,g=g_;
memset(dp,-1,sizeof(dp));
p.clear();
FORE(i,0,n){
stringstream out(platforms[i]);
int t[3];
out>>t[0]>>t[1]>>t[2];
p.push_back(make_pair(make_pair(t[1],t[0]),t[2]));
}
sort(all(p));
int ret=0;
FORE(i,0,n)ret=max(ret,f(i));
return ret;
}
};
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class PlatformJumper {
public:
bool canjump(int x1,int y1,int x2,int y2,int v,int g){
return (double)(x1-x2)*(x1-x2)*g<=2.0*v*v*(double)(y1-y2);
}
int maxCoins(vector<string> platforms, int v, int g) {
int n=platforms.size();
vector<pair<pair<int,int>,int> > p;
FORE(i,0,n){
stringstream out(platforms[i]);
int t[3];
out>>t[0]>>t[1]>>t[2];
p.push_back(make_pair(make_pair(t[1],t[0]),t[2]));
}
sort(p.rbegin(),p.rend());
int dp[n];
FORE(i,0,n)dp[i]=p[i].second;
FORE(i,0,n){
int x1=p[i].first.second,y1=p[i].first.first;
FORE(j,i+1,n){
int x2=p[j].first.second,y2=p[j].first.first;
if(y1>=y2 && canjump(x1,y1,x2,y2,v,g))dp[j]=max(dp[j],dp[i]+p[j].second);
}
}
int ret=0;
FORE(i,0,n)ret=max(ret,dp[i]);
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class PlatformJumper {
public:
bool canjump(int x1,int y1,int x2,int y2,int v,int g){
return (double)(x1-x2)*(x1-x2)*g<=2.0*v*v*(double)(y1-y2);
}
int maxCoins(vector<string> platforms, int v, int g) {
int n=platforms.size();
vector<pair<pair<int,int>,int> > p;
FORE(i,0,n){
stringstream out(platforms[i]);
int t[3];
out>>t[0]>>t[1]>>t[2];
p.push_back(make_pair(make_pair(t[1],t[0]),t[2]));
}
sort(p.rbegin(),p.rend());
int dp[n];
FORE(i,0,n)dp[i]=p[i].second;
FORE(i,0,n){
int x1=p[i].first.second,y1=p[i].first.first;
FORE(j,i+1,n){
int x2=p[j].first.second,y2=p[j].first.first;
if(y1>=y2 && canjump(x1,y1,x2,y2,v,g))dp[j]=max(dp[j],dp[i]+p[j].second);
}
}
int ret=0;
FORE(i,0,n)ret=max(ret,dp[i]);
return ret;
}
};