AcWing 1049 大盗阿福 线性dp

这题不知道为什么打不开，一点进去就是一个课程

题目描述

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

 

这条街上一共有 N 家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。

 

作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？

输入

输入的第一行是一个整数T(T≤50) ，表示一共有T组数据。

接下来的每组数据，第一行是一个整数N(1≤N≤100,000) ，表示一共有N家店铺。第二行是N个被空格分开的正整数，表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过1000。

输出

对于每组数据，输出一行。该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金数量。

样例输入1

2
3
1 8 2
4
10 7 6 14

样例输出1

8
24

这题就是一个很普通的dp

dp三要素写好直接过了

三要素不懂的进来看

The First：状态定义

因为有n个商铺，每个商铺有两种抉择：偷or不偷

我们用f数组表示

f[i]表示第i个商铺最优抉择下的能挣最多的钱

因为有两种可能，所以我们加一个维度

f[i][0]表示不偷 f[i][1]表示偷 dp[i]表示最优抉择

初始化：

1.  
   dp[1]=a[1];
2.  
   dp[2]=max(dp[1],a[2]);
3.  
   a数组表示金额

状态转移方程就很好推了

1.  
   f[i][0]=dp[i-1];//不偷
2.  
   f[i][1]=dp[i-2] a[i];//偷
3.  
   dp[i]=max(f[i][0],f[i][1]);

AC代码（因为题目打不开所以用我们自己OJ提交的）

1.  
   # include <iostream>
2.  
   # include <cstdio>
3.  
   # include <cstring>
4.  
   using namespace std;
5.  
   # define int long long
6.  
   # define N 100005
7.  
   int f[N][2];
8.  
   int dp[N];
9.  
   int n,t;
10.  
    int a[N];
11.  
    signed main(){
12.  
    scanf("%lld",&t);
13.  
    while(t--){
14.  
    memset(f,0,sizeof(f));
15.  
    memset(dp,0,sizeof(dp));
16.  
    scanf("%lld",&n);
17.  
    for (int i=1;i<=n;i ){
18.  
    scanf("%lld",&a[i]);
19.  
    }
20.  
    /*f[1][1]=a[1]=f[2][0];
21.  
    f[1][0]=0;
22.  
    f[2][1]=a[2];*/
23.  
    dp[1]=a[1];
24.  
    dp[2]=max(dp[1],a[2]);
25.  
    for (int i=3;i<=n;i ){
26.  
    f[i][0]=dp[i-1];//不偷
27.  
    f[i][1]=dp[i-2] a[i];//偷
28.  
    dp[i]=max(f[i][0],f[i][1]);
29.  
    }
30.  
    printf("%lld\n",dp[n]);
31.  
    }
32.  
    return 0;
33.  
    }

这篇好文章是转载于：学新通技术网