[raid] [simple DP] mine excavation

link ：

️https://www.luogu.com.cn/problem/P2196️

There are a series of paths in several points , One can walk from a certain point , Until the end , Each point has a value , Ask the maximum value you can get

Because of the small amount of data , So we can conduct a violent search

---

1️⃣ Violent search

• You can start at each point ： So in dfs Some things need to be recorded to flash back , What needs to be traced back in this topic is cnt value ( The number of paths is recorded )
• $g[i][j]$ representative i To j Whether it can reach
• v ： An array of record paths
• sum: Represents the sum of the median values of the path ending with the current point
• Pay attention to the starting point cnt We should also go back

Violent search

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
bool g[21][21],vis[30]; 
int a[25];
int p[25];

int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	memset(g, false, sizeof(g));
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 2; i <= n; i++) 
	{
    
		for(int j = i; j <= n; j++)
		{
    
			int x;
			cin >> x;
			g[i - 1][j] = x;
		}
	}
	int ans = 0;
	vector<int> v;
	int cnt = 0;
	
	function<void(int, int)> dfs = [&](int x, int sum) -> void
	{
    
		for(int i = x + 1; i <= n; i++)
		{
    
			if(g[x][i])
			{
    
				p[++ cnt] = i;
				dfs(i, sum + a[i]);
				cnt --; 
			}
		}
		if(sum > ans)
		{
    
			ans = sum;
			v.clear();
			for(int i = 1; i <= cnt; i++) v.push_back(p[i]);
		}
	};
	for(int i = 1; i <= n; i++)
	{
    
		p[++ cnt] = i;
		dfs(i, a[i]);
		cnt --;
	}
	for(int i = 0; i < v.size(); i++)
		cout << v[i] << " \n"[i == v.size() - 1]; 
	cout << ans << "\n";
	return 0;
}

2️⃣DP

State means ：
$f[i]$: With i Is the maximum value of the sum in the ending path
State shift ：
$f[i]=max(f[j]+a[i],f[i])=max(f[j])+a[i]$

Because the path needs to be recorded , You need to set a pre The precursor node in the array storage path , Finally, use recursive output path .

And also notice that f[i] Initialization of an array , Because sometimes you can choose only one point , If it is not initialized, an error will occur .

last: The end node of the path in the optimal result

#include<bits/stdc++.h>
using namespace std;


int main()
{
    
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	cin >> n;
	vector<int>a(n + 1),f(n + 1);
	vector g(n + 1, vector(n + 1, 0));
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i < n; i++)
		for(int j = i + 1; j <= n; j++)
		{
    
			int x;
			cin >> x;
			g[i][j] = x;
		}
	
	vector<int> pre(n + 1, 0);
	int res = 0;
	int last = 0;
	
	for(int i = 1; i <= n; i++) f[i] = a[i];
	
	for(int i = 2; i <= n; i++)
	{
    
		for(int j = 1; j < i; j++)
		{
    
			if(g[j][i] && f[j] + a[i] > f[i])
			{
    
				f[i] = f[j] + a[i];
				pre[i] = j;
			}
		}
		if(f[i] > res)
		{
    
			last = i;
			res = f[i];
		}
	}
	
	function<void(int)> print = [&](int x) -> void
	{
    
		if(pre[x] == 0)
		{
    
			cout << x ;
			return;
		}
		print(pre[x]);
		cout << " " << x;
	};
	print(last);
	cout << "\n" << res << "\n";
	return 0;
}