信息学奥赛一本通 1301：大盗阿福 | OpenJudge NOI 2.6 8462:大盗阿福

【题目链接】

ybt 1301：大盗阿福
OpenJudge NOI 2.6 8462:大盗阿福

【题目考点】

1. 动态规划：线性动规

【解题思路】

该题可以抽象为：有一个数字序列，选择其中不连续的多个数字构成子序列，求所有这样的子序列中加和最大的子序列的加和。
记a[i]为第i个数字。

1. 状态定义

集合：不连续的数字构成的子序列
限制：在前i个数字中选择数字
属性：加和
条件：最大
统计量：加和
状态定义：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]。
• 以上两种情况求最大值

【题解代码】

解法1：线性动规

#include<bits/stdc++.h>usingnamespacestd;constintN=100005;intn,t,a[N],dp[N];//dp[i]：[1, i]的所有由不相邻元素构成的子序列中加和最大的子序列的加和intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cin>>t;while(t--){cin>>n;for(inti=1;i<=n;++i)cin>>a[i];dp[1]=a[1];for(inti=2;i<=n;++i)dp[i]=max(dp[i-1],dp[i-2]+a[i]);cout<<dp[n]<<'\n';}return0;}