DFS解法

以下是题解
思想是用DFS暴力搜索每条路径，找出最优解

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int n,m,ans = 0;
int passage[110],score[N];
//定义基础变量和数组
void dfs(int x,int new_score){
//定义DFS，x是关数，score是分数
	if(x >= n + 1){
		ans = max(new_score,ans);
        //暴力找出最高分数
		return;
	}else{
		for(int i = 1;i <= m;i++){
			dfs(x + passage[i],new_score + score[x]);
            //暴力去走每条路径
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= m;i++){
		cin >> passage[i];
	}	
	for(int i = 1;i <= n;i++){
		cin >> score[i];
	}
	dfs(1,0);
	cout << ans;
    //输入与输出，ans是答案
	return 0;
}

也是十分简单