[Acwing] 1049. 大盗阿福 状态机|线性DP

前言

一开始 看提高课 状态机模型？(状态机是什么)

结果 线性DP AC了 (懵逼)

前言 : https://www.acwing.com/solution/content/23723/

思路

线性DP ：

看完题目应该就知道 这是很裸的一个模型

用 f [ i ] f[i] f[i] 前 i i i 家 能 偷到的最大金额

那么考虑当前节点 无非就两个状态

• 偷 : f [ i ] = f [ i − 2 ] + w [ i ] f[i] =f[i-2]+w[i] f[i]=f[i−2]+w[i]
• 不偷 : f [ i ] = f [ i − 1 ] f[i] =f[i-1] f[i]=f[i−1]

因此答案就是 m a x ( f [ i − 1 ] , f [ i − 2 ] + w [ i ] ) max(f[i-1],f[i-2]+w[i]) max(f[i−1],f[i−2]+w[i])

状态机 :

可以说是更加合理的一种方法

处理了 : **如果 第 i − 1 i-1 i−1 家被抢,那么第 i i i家的就不能被抢的情况

(貌似 我线性DP也是满足的。。。)

因此对于原先的状态 f [ i ] f[i] f[i]我们再加一维 f [ i ] [ 2 ] f[i][2] f[i][2]

• 0 表示不被抢
• 1 表示被抢

因此状态转移方程变化

f [ i ] [ 1 ] = f [ i − 1 ] [ 0 ] + w [ i ] f[i][1] =f[i-1][0]+w[i] f[i][1]=f[i−1][0]+w[i] f [ i ] [ 0 ] = m a x ( f [ i − 1 ] [ 1 ] , f [ i − 1 ] [ 0 ] ) f[i][0] = max(f[i-1][1] , f[i-1][0]) f[i][0]=max(f[i−1][1],f[i−1][0])

这样子就少用了一层状态 i − 2 i-2 i−2 很不错呢

CODE

#include 
using namespace std;
const int N  = 1e5+10;
int f[N],n;
void solve()
{
    cin>>n;
    int w;
    cin>>w;
    f[1] = w;

    for(int i=2;i>w;
        f[i]=max(f[i-1],f[i-2]+w);
    }
    cout