1301:大盗阿福

2023-12-26 15:28:31

【算法分析】

动态规划:线性动规
该题可以抽象为:有一个数字序列,选择其中不连续的多个数字构成子序列,求所有这样的子序列中加和最大的子序列的加和。
a[i]为第i个数字。

1. 状态定义
状态定义:dp[i]:前i个数字中不连续的数字构成的子序列中,加和最大的子序列的加和。
初始状态:第1个数字构成子序列,加和就是a[1]dp[1] = a[1]

2. 状态转移方程
集合:前i个数字中不连续的数字构成的子序列
分割集合:以该子序列是否包含第i个数字a[i]来分割集合

如果该子序列包含a[i],那么一定不会包含a[i-1]。前i个数字中不连续的数字构成的子序列的最大数字和为:前i-2个数字中不连续的数字构成的子序列的最大数字和再加上a[i]。即dp[i] = dp[i-2] + a[i]
如果该子序列不包含a[i],那么前i个数字中不连续的数字构成的子序列的最大数字和为:前i-1个数字中不连续的数字构成的子序列的最大数字和,即dp[i] = dp[i-1]
以上两种情况求最大值


【参考代码】

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int t, n, a[N], dp[N];//dp[i]:前i个数字中不连续的数字构成的子序列中,加和最大的子序列的加和。
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        dp[1] = a[1];
        for(int i = 2; i <= n; ++i)
            dp[i] = max(dp[i-1], dp[i-2]+a[i]);
        printf("%d\n", dp[n]);
    }
    return 0;
}


?

文章来源:https://blog.csdn.net/pheatonhb/article/details/135222572
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。