問題
１次元の座標をヘビが歩く。
startLocationからスタートし、左か右に移動することができる。
endLocationまでたどり着けばゴールになる。
途中に複数のorbsで示される座標が与えられ、そこにたどり着くと速度が２倍になる。
このとき、ゴールにたどり着くまでの最小の時間を求める。
解き方
制約は座標数＝５０。
これまでにたどり着いた一番左の座標と右の座標、現在左と右のどちらにいるかの状態を持ち、コストを値に持つｄｐを考えればよい。
上記の状態だけあれば、その時のスピードは簡単に計算できるのでスピードの状態を持つ必要はない。
座標にスタートとゴールの位置を足すので、それを踏まえた配列の確保が必要。
グローバル変数の更新に、ローカルでも間違って宣言すると更新されないので注意。
(global int n; local int n=orbs.size() → n=orbs.size();)
コード
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 e,n;
double dp[53][53][2];
vector<int> orb;
class SnakeTurbo {
public:
double dfs(int l,int r,int pos){
if(dp[l][r][pos]!=1e+9)return dp[l][r][pos];
if(orb[l]==e||orb[r]==e)return 0.0;
int dist=( (pos==0) ? orb[l] : orb[r]);
double ret=1e+9;
double speed=1.0;
FORE(i,l,r)speed/=2.0;
if(l-1>=0){
double cost=(dist-orb[l-1])*speed;
ret=min(ret,cost+dfs(l-1,r,0));
}
if(r+1<n){
double cost=(orb[r+1]-dist)*speed;
ret=min(ret,cost+dfs(l,r+1,1));
}
return dp[l][r][pos]=ret;
}
double finishTime(int startLocation, int endLocation, vector<int> orbs) {
orb=orbs;
orb.push_back(startLocation);
orb.push_back(endLocation);
e=endLocation;
n=orb.size();
FORE(i,0,53)FORE(j,0,53)FORE(k,0,2)dp[i][j][k]=1e+9;
sort(all(orb));
int s=-1;
FORE(i,0,n)if(orb[i]==startLocation)s=i;
return dfs(s,s,0);
}
};
#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 e,n;
double dp[53][53][2];
vector<int> orb;
class SnakeTurbo {
public:
double dfs(int l,int r,int pos){
if(dp[l][r][pos]!=1e+9)return dp[l][r][pos];
if(orb[l]==e||orb[r]==e)return 0.0;
int dist=( (pos==0) ? orb[l] : orb[r]);
double ret=1e+9;
double speed=1.0;
FORE(i,l,r)speed/=2.0;
if(l-1>=0){
double cost=(dist-orb[l-1])*speed;
ret=min(ret,cost+dfs(l-1,r,0));
}
if(r+1<n){
double cost=(orb[r+1]-dist)*speed;
ret=min(ret,cost+dfs(l,r+1,1));
}
return dp[l][r][pos]=ret;
}
double finishTime(int startLocation, int endLocation, vector<int> orbs) {
orb=orbs;
orb.push_back(startLocation);
orb.push_back(endLocation);
e=endLocation;
n=orb.size();
FORE(i,0,53)FORE(j,0,53)FORE(k,0,2)dp[i][j][k]=1e+9;
sort(all(orb));
int s=-1;
FORE(i,0,n)if(orb[i]==startLocation)s=i;
return dfs(s,s,0);
}
};