$$\color{Red}{大盗阿福【状态机和线性DP做法】}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。

这条街上一共有 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。

思考

状态机模型和01背包问题的区别
01背包中每个物品选或不选都是独立的，不受前者约束不对后者产生影响，而状态机不一样。
换成01那种状态之间的转化图来看的话,01背包中0和1的转化不受任何约束，可以说是有向完全图。
但是状态机由于某些条件下的边不存在，于是我们在计算本次状态之前就可能需要了解前一次的状态，于是需要状态细分标记

本题可以使用二维的f[i][j]来表示经过i步（也就是选取i个商店后），当前状态为j的最大值（本题j只有0和1也就是选和不选两个状态）

本题思考状态机的状态
状态0（不选当前i步物品）后可以进行 0 -》 0 或者0 -》 1
状态1（选当前i步物品）后可以进行 1-》0
f[i][0] = Math.max(f[i-1][0], f[i-1][1])
f[i][1] = f[i-1][0] + w[i]

java状态机做法

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 100010, T, n;
    static int[][] f = new int[N][2];
    static int[] w = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            n = Integer.parseInt(br.readLine());
            String[] s1 = br.readLine().split(" ");
            for (int i = 1; i <= n; i++)
                w[i] = Integer.parseInt(s1[i - 1]);
            f[1][0] = 0;
            f[1][1] = w[1];
            for (int i = 2; i <= n; i++) {
                f[i][0] = Math.max(f[i-1][0], f[i-1][1]);
                f[i][1] = f[i-1][0] + w[i];
            }
            System.out.println(Math.max(f[n][1], f[n][0]));
        }
    }
}

java背包做法

f[i]表示前i个房间，偷或不偷的状态集合中的最大值，那么我们状态转移的应该是：
选第i个房间：f[i-2] + w[i]
不选第i个房间：f[i-1]
为了防止数组越界，应该从i=2开始转移，那么f[1]应该等于选取第一个物品也就是w[i]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 100010, T, n;
    static int[] f = new int[N];
    static int[] w = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            n = Integer.parseInt(br.readLine());
            String[] s1 = br.readLine().split(" ");
            for (int i = 1; i <= n; i++)
                w[i] = Integer.parseInt(s1[i - 1]);
            f[1] = w[1];
            for (int i = 2; i <= n; i++) 
                f[i] = Math.max(f[i - 2] + w[i], f[i - 1]);
            System.out.println(f[n]);
        }
    }
}