818. Race Car

2018/04/18 21:21
阅读数 34

818. Race Car

原题

题目大意

有3个值:

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

有2个操作:

  • A

    $$position=positionspeed$$ $$speed=2speed$$

  • R

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

求要使$position=target$至少需要几步操作。

思路

BFS

直接对于任一(position,speed)对有两种操作,全部遍历,就可以在第一次达到target时得到结果,且由于ARR操作可以保证所有target都是可以到达的,所有BFS在不限时间的情况下都是可以得到解的。

很显然对于一个最终为n的输入,此方法的时间复杂读为O($2^n$),恕我直言,这要能过,这世界上就没什么不能过了。

优化

一个简单的优化,至少对于绝对值大于target的speed和小于-target和大于2target的position都可以跳过。

另一个简单的优化是对于相同的一对position,speed只入队列一次。在实现上我使用二维数组记录一对position,speed是否出现过,此二维数组的二维分别是speed,position,但是此处有一点,如果考虑speed∈[-target,target]的话,需要的存储空间太大,由于speed的绝对值2的n次方,使用log(|speed|)来记录speed的值,再用另一个变量positive表示speed是正是负。

代码

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(){
            int add = 1<<speed;
            if(!positive) add = -add;
            return new PS(position+add,speed+1,step+1,positive);
        }
        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]

        Queue<PS> q = new LinkedList<>();
        q.add(new PS(0,0,0,true));
        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;
            q.add(psA);
            q.add(ps.doR());
        }
    }

}

DP

设dp[t]表示target为t时,最少需要的步数。

将连续的n次A操作改变的position记为nA,很显然,+iA-jA+kA等价于+kA-jA+iA,同时+iA+kA等价于+kA+iA。

所以当存在一串操作使position始终没有超过t,那么可以首先尽量尝试达到position,也就是说在$position+speed<t$的情况下继续A操作依然可以保证有必要遍历的情况被遍历了。

假设t的二进制表示一共有i位,则iA即可影响到最高位,不需要有(i+1)A,因为若是出现了(i+1)A就必然影响了i+1位,为了使i+1位保持0由以下几种方式,若之前执行的是+(i+1)A,那么就执行-(i+1)A,执行两次+iA,但无疑都多出了许多无意义的操作。

所以要达到一个t,若存在n使得$2^n-1=t$成立,此n就是最佳的步数。否则,设n使$2^{n-1} -1 < target < 2^n -1$成立,则t可以从以下两种的一种中到达。

  • 先到达$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
分享
返回顶部
顶部