这道题我读时想到两种方法，分别是dp和搜索，于是将两种方法奉上
一.dp
这道题的被放在题单“”dp的引入”，所以我们就先用dp思考
dp需要考虑数组，转移方程
1.数组
毫无疑问，这类dp的题都是用一维数组
这道题自然逃不出一维的手掌心
so我们可以用数组dp[i]储存以i为终点的最大地雷数
然后从2进行顺推即可
2.转移方程
我们可以借鉴最长子序列
for(int i=2;i<=n;++i){
dp[i]=0;
for(int j=i-1;j>0;--j){
if(a[i]>a[j]){
dp[i]=max1(dp[i],dp[j]);
}
}
dp[i]++;
if(dp[i]>ans) ans=dp[i];
}由于是单向边，结合输入方式，可知对于点i，只有1到i-1可能存在到点i的路径
用num[i]储存第i个点的地雷数
所以对于dp[i],枚举从j=i-1到j=1
if存在路径并且dp[j]+num[i]>dp[i]
将dp[i]赋值为dp[j]+num[i]
代码实现：
if(a[j][i]&&dp[i]<dp[j]+num[i]){//有路径且大于当前最大值
dp[i]=dp[j]+num[i];
p[i]=j;//更新前驱，i点的上一个点为j
} 所以状态转移方程可总结为：
3.代码
不多说废话了，放出代码，我写了题解，应该能看懂：
#include<bits/stdc++.h>
#define f(x,y) for(register int i=x;i<=y;i++)//宏定义，单纯图省事
using namespace std;
int n;//地窖的个数
bool a[25][25];//联通问题
int num[25];//每个地窖的地雷数量
int p[25];//用来储存第i个点的前驱，既保存路径
int dp[25];//以i为终点的地雷数
int pos;//终点
int ans;//最终结果
void road(int x){//输出路径的函数 ,且为倒序输出
if(p[x]) road(p[x]);//if p[x]的值不为0，说明x不是起点，继续往前搜索
cout<<x<<' ';
return;
}
int main (){
ios::sync_with_stdio(false);//提快cin与cout的速度，懒得写scanf
cin>>n;
f(1,n) cin>>num[i];
f(1,n-1)
for(register int j=i+1;j<=n;j++) {
cin>>a[i][j];
}
dp[1]=num[1];//初始化，以第一个点为终点的地雷树为num[1];
f(2,n){
dp[i]=num[i];//对每个值进行初始化
for(register int j=i-1;j>=1;j--){//i表示的是终点，j表示从j->i
if(a[j][i]&&dp[i]<dp[j]+num[i]){//有路径且大于当前最大值
dp[i]=dp[j]+num[i];
p[i]=j;//更新前驱，i点的上一个点为j
}
}
if(ans<dp[i]) {
ans=dp[i];
pos=i;
}
}
road(pos);
cout<<endl;
cout<<ans;
return 0;
} 二.搜索
由于这道题的数据很水，我们可以直接用搜索来暴力求解
由于是单向边，我的思路是定义一个数组来标记每一个点是否走过
在进行搜索的时候如果不进行标记，会进入死循环
那么搜索时是否有可走的边（有没有被标记过的点&&有联通的边）就很有必要
bool chek(int x){//查看是否还有可走的边
for(int i=1;i<=n;i++)
if(a[x][i]&&b[i]) return true;
return false;
} 路径需要两个数组，一个直接保存答案路径，另一个保存搜索时的路径
如果搜索结果大于当前最大值时，将该路径赋值给结果路径
直接上代码，我写了很详细的注释，应该不难理解：
#include<bits/stdc++.h>
using namespace std;
int ans[25];//储存结果路径
int path[25];//储存DFS路径
bool a[25][25];//储存边是否联通
int n;//地窖个数
int num[25];//每个地窖的地雷数量
bool b[25];//检查每个点是否走过
int anw;//储存最多地雷数
int r;//储存步数
bool chek(int x){//查看是否还有可走的边
for(int i=1;i<=n;i++)
if(a[x][i]&&b[i]) return true;
return false;
}
void DFS(int x,int temp,int cnt){
/*x储存现在所在的点
cnt储存结果
temp储存步数*/
if(!chek(x)){//如果没有可走之路
if(cnt>anw){
anw=cnt;
r=temp;
for(int i=1;i<=r;i++){
ans[i]=path[i];
}
}
return ;
}
for(int i=1;i<=n;i++){
if(a[x][i]&&b[i]){
b[i]=0;//标记
path[temp+1]=i;//记录路径
DFS(i,temp+1,cnt+num[i]);
b[i]=1;//回溯
}
}
}
int main (){
ios::sync_with_stdio(false);
memset(b,1,sizeof(b));
cin>>n;
for(int i=1;i<=n;i++) cin>>num[i];
for(int i=1;i<n;i++)
for(int j=i+1;j<=n;j++){
cin>>a[i][j];//这里是单向边 ，题目没写清楚，我也是质疑题目出错啦
}
for(int i=1;i<=n;i++){
b[i]=0;
path[1]=i;
DFS(i,1,num[i]);
b[0]=0;
}
for(int i=1;i<=r;i++){
cout<<ans[i]<<" ";
}
cout<<endl;
cout<<anw;
return 0;
} 希望能给你提供一些帮助