大家好，本入是一个小小的蒟蒻，所以名气不够，希望各位红名大佬能帮忙宣传一下

事情是这样的：这天我闲来无事，刷着六级题，发现了这道题，一看题目标签"动态规划DP"发现天塌了(因为我DP不熟)，于是想用其他方法做，结果还真AC了，又发现题解和讨论区都没提到这个方法，但我又无法联系管理员，只能来发个讨论区帖子了，希望各位大佬能帮忙@一下管理员和作者，好了不多废话，上方法：

首先，我发现这道题好像不止可以用DP，深搜DFS好像也可以，于是我先手搓了一个普通DFS：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e4+10;

ll n,m,a[N],b[N];

ll dfs(ll x)
{
	if(x>n)
	{
		return 0;
	}
	ll k=-2e9;
	for(int i=1;i<=m;i++)
	{
		k=max(k,dfs(x+a[i]));
	}
	return k+b[x];
}

int main()
{
	cin >> n >> m;
	for(int i=1;i<=m;i++) cin >> a[i];
	for(int i=1;i<=n;i++) cin >> b[i];
	cout << dfs(1) << endl;
	return 0;
}

呵呵，不出所料，TLE了：

于是我们要优化，我们可以发现，同一个位置如 $5$ ，他可以被 $4+1$ 搜一遍，也可以 $3+2$ 搜一遍，为了避免多次重复搜，于是我们可以用 $ans_i$ 储存第 $i$ 个位置的 dfs( $i$ ) 的结果，重复时直接拿来用。于是，每个位置只会被搜一遍，那么时间复杂度就变成了$O(N)$，这个方法俗称记忆化搜索，完结撒花！（了吗？）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e4+10;

ll n,m,a[N],b[N],ans[N];

ll dfs(ll x)
{
	if(x>n)
	{
		return 0;
	}
	if(ans[x]==0)
	{
		for(int i=1;i<=m;i++)
		{
			ans[x]=max(ans[x],dfs(x+a[i]));
		}
	}
	return ans[x]+b[x];
}

int main()
{
	cin >> n >> m;
	for(int i=1;i<=m;i++) cin >> a[i];
	for(int i=1;i<=n;i++) cin >> b[i];
	cout << dfs(1) << endl;
	return 0;
}

提交后……

……，好吧，这里可能因为作者本入代码能力还是其他乱七八糟问题，最简单的第一个点居然WA了，感兴趣的大佬可以帮我查查错。总之，本蒟蒻没有发现我自己哪错了，于是在输出前加了个特判：

if(m==1)
{
	ll p=0;
	for(int i=1;i<=n;i+=a[1])
	{
		p+=b[i];
	}
	cout << p << endl;
	return 0;
}

呵呵，AC了（总代码和图片就不放了，太长了）

总结：希望各位大佬能宣传本帖子，建议作者加上标签“深度优先搜索 DFS”和“记忆化搜索”，如果各位大佬们有能力也可以发布题解（可以直接复制我的这篇，加上原作者声明就可以了哈^v^）

广告：

• 本帖子作者（关注一下吧）
• 特星工作室
• 【五十六】历险记