大盗阿福.java

package dp.状态机模型;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。
 * 这条街上一共有 N家店铺，每家店中都有一些现金。
 * 阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
 * 作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。
 * 他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？
 * 输入的第一行是一个整数 T，表示一共有 T组数据。
 * 接下来的每组数据，第一行是一个整数 N，表示一共有 N家店铺。
 * 第二行是 N个被空格分开的正整数，表示每一家店铺中的现金数量。
 * 每家店铺中的现金数量均不超过1000。
 * 输出格式
 * 对于每组数据，输出一行。
 * 该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。
 * 数据范围
 * 1≤T≤50,
 * 1≤N≤10^5
 * 输入样例：
 * 2
 * 3
 * 1 8 2
 * 4
 * 10 7 6 14
 * 输出样例：
 * 8
 * 24
 * 样例解释
 * 对于第一组样例，阿福选择第2家店铺行窃，获得的现金数量为8。
 * 对于第二组样例，阿福选择第1和4家店铺行窃，获得的现金数量为10+14=24。
 * 分析：
 * 方法一：线性DP
 * 作为一个典型的线性dp问题，本题可以用线性DP的解法来解决。
 * 状态表示f[i]表示在前i家店铺中能够获得的最多的现金。
 * 如果第i家店铺不洗劫，则获得的现金与在前i-1家店铺获得的最大现金一致，
 * 即f[i] = f[i-1]；如果第i家店铺洗劫，则第i-1家店铺不能洗劫，
 * 否则会触发报警器，故此时f[i] = f[i-2] + w，w表示洗劫第i家店铺可以获得的现金。
 * 故状态转移方程为f[i] = max(f[i-1],f[i-2]+w),i >= 2。
 * 这里的边界状态为f[0] = 0,f[1] = w1，因为只有一家商铺时选择洗劫必然是最优选择。
 * dp.状态机模型:
 * 有限状态机（Finite-state machine）又称有限状态自动机，
 * 是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。
 * 在本题中，当我们从前往后遍历到第i个商店时，用0表示不洗劫该商店，1表示洗劫该商店。
 * 则当前状态为洗劫了第i个商店时，状态为1，下一个商店只能不洗劫，
 * 即状态1只能转移到状态0；当前状态为0，即没有洗劫第i个商店时，
 * 下一个状态可以不洗劫也可以洗劫，即状态0既可以转移到状态0，也可以转移到状态1，
 * 本题的状态机如上图所示。
 * 设f[i]0]表示在前i家店铺中不洗劫第i家店铺，
 * f[i][1]表示洗劫第i家店铺，
 * 状态转移方程为f[i][1] = f[i-1][0] + w，f[i][0] = max(f[i-1][0],f[i-1][1])，
 * 最后要求的最大现金等于max(f[n][0],f[n][1])
 * <p>
 * 相当于0 1两个点的图,三条边转移方式
 * 0->1
 * 0->0
 * 1->0
 * 令f[i][0]代表不抢第i家店铺
 */
public class 大盗阿福 {
    public static void main(String[] args) {
        fin();
    }

    //dp.线性dp
    static void lindp() {
        Scanner sc = new Scanner(System.in);
        t = sc.nextInt();
        while (t-- != 0) {
            n = sc.nextInt();
            Arrays.fill(dp, 0);
            for (int i = 0; i < n; i++) {
                a[i] = sc.nextInt();
            }
            dp[1] = a[0];
            for (int i = 2; i <= n; i++) {
                dp[i] = Math.max(dp[i - 1], dp[i - 2] + a[i - 1]);
            }
            System.out.println(dp[n]);
        }
    }

    //状态机

    /**
     * 状态转移,看成图论问题
     * f[i,0] f[i,1] 表示:所有走了i步,且当前位于状态j的所有走法
     * 属性:max
     * 状态计算:f[i,0]   0->0  上一个不偷,这个一个也不偷, f[i-1,0]
     * 1->0  上一个偷了,这个不偷  f[i-1,1]
     * f[i,1] 状态计算,只能0->1 上个不偷这个偷,f[i-1,0]+w[i]
     */
    static void fin() {
        Scanner sc = new Scanner(System.in);
        t = sc.nextInt();
        while (t-- != 0) {
            n = sc.nextInt();
            Arrays.fill(dp, 0);
            for (int i = 1; i <= n; i++) {
                a[i] = sc.nextInt();
            }
            //从1开始没有边界问题
            for (int i = 1; i <= n; i++) {
                //考虑last
                //从上一个也不选,或者上一个选转移过来
                f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]);
                f[i][1] = f[i - 1][0] + a[i];
                //从上一个不选转移过来
            }
            System.out.println(Math.max(f[n][0], f[n][1]));
        }
    }

    static int[][] f = new int[100050][2];
    static int[] dp = new int[100050];
    static int[] a = new int[100050];
    static int t, n;
}