洛谷P2196 && caioj 1415 动态规划6：挖地雷

没看出来动规怎么做，看到n <= 20,直接一波暴搜，过了。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 25;

int g[MAXN][MAXN], a[MAXN], f[MAXN];

int vis[MAXN], path[MAXN], n;

int dfs(int cur)

{

	vis[cur] = 1;

	int t = 0;

	REP(i, 0, n)

		if(!vis[i] && g[cur][i])

		{

			int temp = dfs(i);

			if(t < temp)

			{

				t = temp;

				path[cur] = i;

			}

		}

	vis[cur] = 0;

	return a[cur] + t;

}

int main()

{

	scanf("%d", &n);

	REP(i, 0, n) scanf("%d", &a[i]);

	REP(i, 0, n)

		REP(j, i + 1, n)

			scanf("%d", &g[i][j]);

	int ans = 0, st;

	REP(i, 0, n)

	{

		memset(path, -1, sizeof(path));

		memset(vis, 0, sizeof(vis));

		int t = dfs(i);

		if(ans < t)

		{

			st = i;

			ans = t;

			memcpy(f, path, sizeof(f));

		}

	}

	for(int p = st; p != -1; p = f[p]) printf("%d ", p + 1);

	puts("");

	printf("%d\n", ans);

    return 0;

}

然后我还是想想动规怎么做吧

因为只能往下挖，所以最后一个地窖是挖不了的

所以我们倒着推

我们设f[i]为从i开始能挖到的最大地雷

那么有

f[i] = f[j] + a[i]; i < j, i与j连接

#include<cstdio>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 25;

int g[MAXN][MAXN], a[MAXN], f[MAXN];

int path[MAXN], n;

int main()

{

	memset(path, -1, sizeof(path));

	scanf("%d", &n);

	REP(i, 0, n) scanf("%d", &a[i]);

	REP(i, 0, n)

		REP(j, i + 1, n)

			scanf("%d", &g[i][j]);

	int ans = 0, st;

	for(int i = n - 1; i >= 0; i--)

	{

		f[i] = a[i];

		REP(j, i + 1, n)

			if(g[i][j] && f[i] < f[j] + a[i])

			{

				f[i] = f[j] + a[i];

				path[i] = j;

			}

		if(ans < f[i])

		{

			ans = f[i];

			st = i;

		}

	}

	for(int p = st; p != -1; p = path[p]) printf("%d ", p + 1);

	puts("");

	printf("%d\n", ans);

    return 0;

}