题目链接：https://www.luogu.com.cn/problem/P2196

大意：有n个地窖，每个地窖里有一些地雷，给出第i个地窖到i+1 - n的连通性。求出最优解及路径，要求拆除地雷最多。

这个题可以爆搜（因为n的值很小），也可以dp（类似于最长子序列那种，这里不同的是需要考虑连通性）

这个题看着不难但是自己dfs写的并不是很好，所以wa了，dp做法也看不出来个之所以然

这个题也没有很多需要注意的地方，可能dp写法的状态转移和表示是需要好好分析一下的，其实就是看爆搜的水平和一些dp的分析，这两个确确实实都是我的弱项。emm~代码还是挺简单的，这里的dpi表示为以i为终点的最优解。i受到的影响应该是前几个节点。这样就从i-1到1来转移到dpi。可以看到我们转移状态的时候是用前面的状态来转移的，所以外循环要从小到大开始，把之前的最优子状态算好了，再推导我们之后的状态。

爆搜code：

#include<bits/stdc++.h>
using namespace std;
int cellar[25],mapt[25][25],path[25],ans[25];
int n,k,maxt = 0,cnt;
bool sign[25];

bool check(int x)
{
	for(int i=1;i<=n;i++)
		if(mapt[x][i]&&!sign[i])	return false;
	return true;
}
void dfs(int x,int step,int sum)
{
	if(check(x))
	{
		if(sum>maxt)
		{
			memcpy(ans,path,sizeof path);
			maxt = sum;
			cnt = step-1;
		}
		return;
	}
	for(int i=1;i<=n;i++)
		if(mapt[x][i]&&!sign[i]) 
		{
			sign[i] = true; path[step] = i;
			dfs(i,step+1,sum+cellar[i]);
			sign[i] = false;
		}	
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&cellar[i]);
	for(int i=1;i<=n;i++)
	for(int j=i+1;j<=n;j++)
	{
		scanf("%d",&k);
		if(k)	mapt[i][j] = 1; else	mapt[i][j] = 0;
	}
	for(int i=1;i<=n;i++)
	{
		sign[i] = true;
		path[1] = i;
		dfs(i,2,cellar[i]);
	}
	for(int i=1;i<=cnt;i++)
		printf("%d%c",ans[i],i==cnt?'\n':' ');
	printf("%d",maxt);
}

dpcode：

#include<bits/stdc++.h>
using namespace std;
int cellar[25],mapt[25][25],path[25],ans[25];
int n,k,maxt = 0,cnt;
bool sign[25];

bool check(int x)
{
	for(int i=1;i<=n;i++)
		if(mapt[x][i]&&!sign[i])	return false;
	return true;
}
void dfs(int x,int step,int sum)
{
	if(check(x))
	{
		if(sum>maxt)
		{
			memcpy(ans,path,sizeof path);
			maxt = sum;
			cnt = step-1;
		}
		return;
	}
	for(int i=1;i<=n;i++)
		if(mapt[x][i]&&!sign[i]) 
		{
			sign[i] = true; path[step] = i;
			dfs(i,step+1,sum+cellar[i]);
			sign[i] = false;
		}	
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&cellar[i]);
	for(int i=1;i<=n;i++)
	for(int j=i+1;j<=n;j++)
	{
		scanf("%d",&k);
		if(k)	mapt[i][j] = 1; else	mapt[i][j] = 0;
	}
	for(int i=1;i<=n;i++)
	{
		sign[i] = true;
		path[1] = i;
		dfs(i,2,cellar[i]);
	}
	for(int i=1;i<=cnt;i++)
		printf("%d%c",ans[i],i==cnt?'\n':' ');
	printf("%d",maxt);
}