Topic Portal

When I read this question, I thought of two ways, dp and search, so I gave them two ways

1.dp

This question is put on the introduction of the "dp" on the form, so let's think about it with DP first

dp needs to consider array, transfer equation

1. Arrays

Undoubtedly, this type of dp question uses a one-dimensional array

This question can't escape the palm of one dimension naturally

so we can use the array dp[i] to store the maximum number of mines that end with I

Then push forward from 2

2. Transfer equation

We can learn from the longest subsequence

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];
	}

Since it is a one-way edge, combined with the input method, it is known that for point i, only one to i-1 may have a path to point I

Number of Mines stored at point I I with num[i]

So for dp[i], the enumeration goes from j=i-1 to j=1

if there is a path and dp[j]+num[i]>dp[i]

Assign dp[i] to dp[j]+num[i]

Code implementation:

	if(a[j][i]&&dp[i]<dp[j]+num[i]){//Path and greater than current maximum 
				dp[i]=dp[j]+num[i];
				p[i]=j;//Update precursor, the last point on point i is j 
	}	

So the state transfer equation can be summarized as:

dp[i]=a[i]+max(dp[1],dp[2],,,dp[i-1]);

3. Code

No more crap, release the code, I wrote a caption, you should understand:

#include<bits/stdc++.h>
#Define f(x,y) for(register int i=x; i<=y; i++)//macro definition, simplicity 
using namespace std;
int n;//Number of Basements
bool a[25][25];//Connectivity issues
int num[25];//Number of Mines per cellar 
int p[25];//Used to store the pioneer of point I i, saving both paths
int dp[25];//Number of Mines ending with i
int pos;//End
int ans;//final result 
void road(int x){//A function of the output path, in reverse order 
	if(p[x]) road(p[x]);//The value of if p[x] is not zero, indicating that x is not the starting point, and continue searching forward 
	cout<<x<<' ';
	return;
} 
int main (){
	ios::sync_with_stdio(false);//Speed up cin and cout, lazy to write 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];//Initialize with num[1] as the mine tree ending at the first point;
	f(2,n){
		dp[i]=num[i];//Initialize each value 
		for(register int j=i-1;j>=1;j--){//I denotes the end point, J denotes from j->i
			if(a[j][i]&&dp[i]<dp[j]+num[i]){//Path and greater than current maximum 
				dp[i]=dp[j]+num[i];
				p[i]=j;//Update precursor, the last point on point i is j 
			}	
		} 
		if(ans<dp[i]) {
			ans=dp[i];
			pos=i;
		} 
	}
	road(pos);
	cout<<endl;
	cout<<ans; 
	return 0;
} 

2. Search

Since the data on this question is fairly watery, we can use search directly to solve it violently

Since it's a one-way edge, my idea is to define an array to mark whether each point has passed or not

If you don't mark it when searching, it goes into a dead loop

Then it's important to have a walking edge (if there are any marked points & connected edges) when searching

bool chek(int x){//Check to see if there are any walking edges 
	for(int i=1;i<=n;i++)	
		if(a[x][i]&&b[i]) return true;
	return false;
} 

Path requires two arrays, one to save the answer path directly and the other to save the path when searching

If the search result is greater than the current maximum, assign the path to the result path

Directly to the code, I wrote a very detailed comment, which should not be difficult to understand:

#include<bits/stdc++.h>
using namespace std;
int ans[25];//Store result path 
int path[25];//Store DFS Path 
bool a[25][25];//Storage Edge Connectivity 
int n;//Number of Basements 
int num[25];//Number of Mines per cellar
bool b[25];//Check whether each point has passed
int anw;//Maximum number of Mines stored 
int r;//Storage steps 
bool chek(int x){//Check to see if there are any walking edges 
	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 Store the point where you are now
  cnt Store results 	
  temp Storage steps*/			 								 	 
	if(!chek(x)){//If there is no way to go 
		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;//sign 
			path[temp+1]=i;//Record Path 
			DFS(i,temp+1,cnt+num[i]);
			b[i]=1;//To flash back 
		}
	}
	
}
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];//This is a one-way side, the title is not clearly written, I also question the title is wrong 
	}
	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;
} 

I hope you can get some help