題目

我們的黑虎阿福改行當小偷啦!然后他去偷東西，然后那個zz報警系統只有在他洗劫兩家相鄰的店才會報警，然后求他在不觸發警報的情況下能拿到最多的錢。
（注：沒有偷了會扣錢的店鋪）

---

輸入

2
3
1 8 2
4
10 7 6 14

輸入

8
24

樣例解釋

對于第一組樣例，阿福選擇第 2 家店鋪行竊，獲得的現金數量為 8 。
對于第二組樣例，阿福選擇第 1 和 4 家店鋪行竊，獲得的現金數量為 10 + 14 = 24 。

---

解題思路

他只有兩種情況，就是間隔一個或間隔兩個再洗劫。因為如果間隔三個那不如把中間的那家也洗劫掉。
所以：
f[i]=max(f[i-2],f[i-3])+a[i];

---

代碼（有什么好解釋？）

#include<cstdio> #include<iostream> using namespace std; int n,t,a[100001],f[100001]; int main() {scanf("%d",&t);for (int t1=1;t1<=t;t1++){scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]),f[i]=0;f[1]=a[1];f[2]=a[2];for (int i=3;i<=n;i++)f[i]=max(f[i-2],f[i-3])+a[i];printf("%d\n",max(f[n],f[n-1]));} }

總結

以上是生活随笔為你收集整理的OJ8462-大盗阿福【各种dp之5】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。