摘要
Title: 1049. 大盗阿福
Tag: 状态机模型、dp
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

1049. 大盗阿福

• 题意

  阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。
  这条街上一共有 NN 家店铺，每家店中都有一些现金。
  阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
  作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。
  他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？

• 思路

  $f[i]$ 表示前 $i$ 个店铺的最大收益

  • 不抢第 $i$ 个店铺时的最大收益为 $f[i-1]$
  • 抢第 $i$ 个店铺时的最大收益位$f[i-2]+w[i]$

  当$i>1$时，$f[i]=max(f[i-1],f[i-2]+w[i])$

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-03-13 21:23:33
  FilePath: \ACM\Acwing\1049.py
  LastEditTime: 2022-03-13 21:23:34
  '''
  for _ in range(int(input())):
      N = int(1e5 + 10)
      dp = [0] * N
      w = [0] * N
      n = int(input())
      w[1:] = list(map(int, input().split()))
  
      dp[1] = w[1]
      for i in range(2, n + 1):
          dp[i] = max(dp[i - 1], dp[i - 2] + w[i])
      print(dp[n])