T1 100%

T2 100%

前兩個(gè)都是模擬，沒啥說的。

T3 100%

跳躍游戲，有n+1個(gè)點(diǎn)，從0跳到n。有四種跳躍方式（跳一格、兩個(gè)、三個(gè)、四個(gè)），逐一選擇，全都選完一遍后會(huì)刷新。跳躍點(diǎn)上有金幣，不能讓自己金幣為負(fù)數(shù)。

常規(guī)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等價(jià)
                        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，因?yàn)榱?xí)慣DFS+cache的寫法，但是下面代碼好像有問題，從0位置開始，沒法知道后續(xù)選擇是否成立。還得從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;
    }