2018/04/18 21:21

# 818. Race Car

## 题目大意

• position 初值 0
• speed 初值 1
• target

• A

$position=positionspeed$ $speed=2speed$

• R

$position=position$ $speed=\begin{cases} -1& \text{ if } speed>0 \ 1 & \text{ if } speed \leq 0 \end{cases}$

## 思路

### BFS

#### 代码

Java:

class Solution {
private static class PS{
//Position and Speed
int position;
int speed;
int step;
boolean positive;

PS(int position, int speed, int step, boolean positive) {
this.position = position;
this.speed = speed;
this.step = step;
this.positive = positive;
}
PS doA(){
}
PS doR(){
return new PS(position,0,step+1,!positive);
}
}
public int racecar(int target) {
int nt = -target;
int t2 = 2*target;

boolean [][] v = new boolean[28][3*target];//[speed][position]

int iSpeed,iPosition;
while(true){
PS ps = q.remove();
if(ps.position>=t2||ps.position<=nt||ps.speed>=14) continue;
iSpeed = ps.speed + (ps.positive?14:0);
iPosition = ps.position + target;
if(v[iSpeed][iPosition]) continue;
else v[iSpeed][iPosition] = true;
PS psA = ps.doA();
if(psA.position==target) return psA.step;
}
}

}


### DP

• 先到达$2^n-1$再经过一个R操作和dp[$2^n-1-t$]次操作回到t。
• 先到达$2^{n-1}-1$再经过R操作、i个A操作、R操作、dp[$t-2^{n-1}+2^i$]操作回到t，其中$i<n-1$

#### 代码

C++

class Solution {
public:
int dp[10001];

int racecar(int t) {
if(dp[t]!=0)return dp[t];
int n = floor(log2(t)) + 1;
if (1 << n == t + 1) dp[t] = n;
else{
dp[t] = n + 1 + racecar((1<<n)-1-t);//2^n-1、R、dp[2^n-1-t]
for(int i=0;i<n-1;i++)//2^{n-1}-1、R、i个A、R、dp[t-2^{n-1}+2^i}]
dp[t] = min(dp[t],n+i+1+racecar(t-(1<<(n-1))+(1<<i)));
}
return dp[t];
}
};


0
0 收藏

0 评论
0 收藏
0