背景

今天刚学了DP，但还是想用DFS做这道题。

---

取数

题目自己看吧。

---

DP写法

毕竟这是DP的题目，先用DP做这道题。

1. 分析

标签就是动态规划……而且我看不出什么无后效性。

还是用DP吧。

2. 定义状态变量

定义一个 dp 数组，表示前 i 个数 最大可以取到多少。

3. 状态转移方程

对于任意一个 i ，可以得到两种状态：

1. 选择第 i 项：那么不能选前一项。$dp[i]=dp[i-2]+a[i]$；
2. 不选第 i 项：继续保留前一项。$dp[i]=dp[i-1]$。

得到状态转移方程：

$$dp[i] = \begin{cases} 选 a_i & dp[i-2]+a[i]\\ 不选 a_i & dp[i-1] \end{cases} $$

4. 初始状态和边界

dp[1] 肯定等于 a[1]，这没什么好解释的。

之后就是递推了。

代码

---

DFS写法

这个想法是在今天集训时想到的。就是用前缀和来优化，如果当前的数加上剩下所有数（假设都能选，不然太复杂了）都不能达到当前最大的答案，直接结束就好了。其他的就按照D老师上课讲的就好了。核心代码：

//保持不变，增加前缀和数组 
void dfs(int k, int p)
{
	//如果当前的数加上剩下所有数（假设都能选）都不能达到最大答案，直接结束
    if (cnt + (s[n] - s[p]) < ans)return;
    //保持不变 
}
int main()
{
    //保持不变，增加前缀和数组初始化 
    return 0;
}

完整版