P2196 [NOIP1996 提高组] 挖地雷

网址如下：

P2196 [NOIP1996 提高组] 挖地雷 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

早上看二进制下标树看到一半被高中同学要求看看这一题

他只说看看，也没问什么东西，怪

就做了一下

思路还算是简单的

dp值代表在这个地窖的最大炸弹数（虽然说起点随便，但是路径是向后的）（虽然我dp的名字用的是bomb）

path的值表示从这个地窖通往下一个最多炸弹数的地窖（后面加起来的炸弹数）

再用一个beginning记录起点，maxn记录最大炸弹数（好像也不需要）

最后输出就是了

代码如下：

#include<iostream>
using namespace std;
bool condition[21][21];
int bomb[21], path[21], beginning, maxn, N;

int main(void)
{
	//输入
	cin >> N;
	for(int i = 1; i <= N; i++)
		cin >> bomb[i];
	for(int i = 1; i < N; i++)
		for(int j = i + 1; j <= N; j++)
		{
			int tmp;
			cin >> tmp;
			condition[i][j] = (bool)tmp;
		}
	//处理
	for(int i = N; i; i--)
	{
		int n_tmp = 0;
		for(int j = i + 1; j <= N; j++)
			if(condition[i][j] && n_tmp < bomb[j])
				n_tmp = bomb[j], path[i] = j;
		bomb[i] += n_tmp;
		if(maxn < bomb[i])
			maxn = bomb[i], beginning = i;
	}
	//输出
	cout << beginning;
	for(int i = path[beginning]; i; i = path[i])
		cout << ' ' <<  i;
	cout << endl << maxn;

	return 0;
}