P2196 [NOIP1996 提高组] 挖地雷 [基础DP]

         说实话看到这道题的时候第一眼想到的就是——最短路，但本题的标答是DP于是就有了一笑的题解。但其实提交的时候很无语，不知为啥会WA个点，后面发现是路径输出没有按从小到大排序，**就很离谱，题目也没要求！！！**

        其次其实dp的公式很简单，就在代码里这里就不多讲了，主要是路径的问题。

#include<iostream>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<string>
#include<cmath>
#include<string>
#include<string.h>
//priority_q
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define int long long
//s.find 未找到返回 string::npos
using namespace std;
int dp[300];
int mp[300];
int path[300];
int ans[304];
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	/*int t = 0;
	cin >> t;
	while (t--)
	{


	}*/
	int n; cin >> n;
	int cnt_ans = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> mp[i];
		dp[i] = mp[i];//从每个位置开始的初始值都是他本身
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			int x;
			cin >> x;
			if (dp[i] + mp[j] > dp[j]&&x)//我用的是“我为人人”的想法，另一种是“人人为我”
			{
				dp[j] = dp[i] + mp[j];
				path[j] = i;//设立记录路径
			}
			//cout << x << " ";
		}
		//cout << endl;
	}

	int k = 0;
	for (int i = 1; i <= n; i++)
	{
		/*cout << dp[i] << " ";*/
		if (dp[i] > dp[k])
		{
			k = i;//因为答案默认从小到大排序，所以可以从dp[i]最大的点倒推路径
		}
	}
	int mx = dp[k];
	ans[++cnt_ans] = k;
	k = path[k];
	while (k)
	{
		ans[++cnt_ans] = k;
		k = path[k];
	}
	for (int i = cnt_ans; 1 <= i; i--)
	{
		cout << ans[i] << " ";
	}
	cout << endl;
	cout << mx << endl;
}