C3-D 导弹轰炸

题目描述

AA 国有 nn 个前哨站，每个前哨站有一个重要程度 wiw_i，现在你是 BB 国的总指挥，想要使用你们的导弹轰炸$ A$ 国的前哨站。可惜的是BB 国的导弹在轰炸相邻的两个前哨站会产生干扰导致导弹失效。

现在你想知道在导弹互不干扰的情况下，能够轰炸的前哨站的重要程度之和的最大值为多少。

输入格式

第一行包含一个整数$ t$ ，表示测试数据的数量，接下来 tt 组测试数据。

每组测试数据包含两行。

第一行包含一个正整数 n(2≤n≤105)n(2≤n≤105)，含义如上。

第二行包含 nn 个正整数 w1,w2,…,wn(1≤wi≤105)w_1,w_2,…,w_n(1≤w_i≤105)，表示每个前哨站的重要程度。

数据保证 ∑n≤4⋅105∑n≤4⋅10^5 。

输出格式

对于每组测试数据，输出一行一个整数，表示在导弹互不干扰的情况下，能够轰炸的前哨站的重要程度之和的最大值。

题目分析

先从1个站台考虑，此时答案为w1w_1；当有2个站台时，答案为max(w1,w2)max(w_1,w_2)；当有3个站台，答案为max(w1+w3,w2)max(w_1+w_3,w_2)；

当有nn个站台时，如果打击了n−1n-1号站台那就无法打击nn号站台，此时可等效为只有n−1n-1号站台。反之如果打击了nn号站台，则n−1n-1号一定没有被打击，此时状态由n−2n-2时的状态转移。dp[i]dp[i]表示在1−i1-i中打击的最优结果，易得状态转移方程：

dp[i]=max(dp[i−1],dp[i−2]+wi)dp[i]=max(dp[i-1],dp[i-2]+w_i)

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
int w[100010];
long long int dp[100010];
long long int ans(int n)
{
    if (n == 0)
        return 0;
    if (n == 1)
        return w[0];
    dp[0] = w[0];
    dp[1] = (w[0] > w[1]) ? w[0] : w[1];
    for (int i = 2; i < n; i++)
    {
        dp[i] = (dp[i - 1] > (dp[i - 2] + w[i])) ? dp[i - 1] : (dp[i - 2] + w[i]);
    }

    return dp[n - 1]; 
}

int main()
{
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++)
    {
        int n;
        scanf("%d", &n);
        for (int j = 0; j < n; j++)
        {
            scanf("%d", &w[j]);
        }
        printf("%lld\n", ans(n));
    }
    return 0;
}