得物笔试AK

T1 100%

T2 100%

前两个都是模拟，没啥说的。

T3 100%

跳跃游戏，有n+1个点，从0跳到n。有四种跳跃方式（跳一格、两个、三个、四个），逐一选择，全都选完一遍后会刷新。跳跃点上有金币，不能让自己金币为负数。

常规DP解决。

        for(int i = 1; i <= n; i++) a[i] = in.nextLong();
        long[][] dp = new long[n+1][15];
        for(int i = 0; i <= n; i++) for(int j = 0; j < 15; j++) dp[i][j] = -1;
        dp[0][0] = 0;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < 15; j++){
                for(int l = 0; l < 4; l++){
                    if((j & (1 << l)) == 0){
                        // 0和15等价
                        int p = (j + (1 << l)) == 15 ? 0 : (j + (1 << l));
                        if(i - (l + 1) >= 0 && dp[i-(l+1)][p] != -1){
                            dp[i][j] = Math.max(dp[i][j], a[i] + dp[i-(l+1)][p]);
                        }
                    }
                }
            }
        }
        for(int i = 0; i < 15; i++) res = Math.max(res, dp[n][i]);
        System.out.println(res);

写的第一版代码不是DP，因为习惯DFS+cache的写法，但是下面代码好像有问题，从0位置开始，没法知道后续选择是否成立。还得从n开始，map里面放的是前面位置的元素（和dp一样）。

    public long dfs(int ind, int p, long cur){
        if(ind == n) return 0;
        int key = ((ind << 10) | p);
        if(mp.containsKey(key)) return mp.get(key);
        long ans = -1;
        for(int i = 1; i <= 4; i++){
            if((p & (1 << i)) != 0 && (ind + i) <= n){
                int nind = ind + i;
                int np = (p - (1 << i)) == 0 ? 30 : (p - (1 << i));
                long ncur = cur + a[ind + i];
                // long cans = dfs(nind, np, ncur);
                if(dfs(nind, np, ncur) != -1){
                    ans = Math.max(ans, a[ind + i] + dfs(nind, np, ncur));
                }
            }
        }
        mp.put(key, ans);
        return ans;
    }