洛谷P1854 花店橱窗布置

DP，直接递推比记忆化搜索简单。

定义状态\(dp[i][j]\)为前i行最后一个选择第i行第j个数所得到最大值。

易得状态转移方程

\(dp[i][j]=max(dp[i-1][k]+a[i][j])\)

这个题比较困难的就是在\(j\)和\(k\)的枚举上。\(j\)要满足选\(j\)的时候一定要比\(i\)大，比\((m-(n-i))\)小，只有这样才能使前i朵花都可选，后i朵花都可选。而k因为在上一行，所以只需要比j小就好。

#include <bits/stdc++.h>

using namespace std;

const int _INF = -2054847099;

int n, m, maxn;

int a[1001][1001];

//dp[i][j]是必须选择第i，j个数的最大值。

int dp[1001][1001], pre[1001][1001];

int main()

{

 	memset(dp, -123, sizeof(dp));

 	scanf("%d%d", &n, &m);

 	for (int i = 1; i <= n; i++)

 		for (int j = 1; j <= m; j++)

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

 	for (int i = 1; i <= m; i++)

 		dp[1][i] = a[1][i];

 	for (int i = 2; i <= n; i++)

		for (int j = i; j <= m - (n - i); j++)

		{

			for (int k = 1; k < j; k++)

			{

				if (dp[i][j] < dp[i - 1][k] + a[i][j])

				{

					dp[i][j] = dp[i - 1][k] + a[i][j];

					pre[i][j] = k;

				}

			}

		}

	int maxn = 0, maxk;

	for (int i = 1; i <= m; i++)

		if (maxn < dp[n][i])

		{

			maxn = dp[n][i];

			maxk = i;

		}

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

	stack <int> s;

	s.push(maxk);

	while (n)

	{

		maxk = pre[n--][maxk];

		s.push(maxk);

	}

	s.pop();

	while (s.size())

	{

		printf("%d ", s.top());

		s.pop();

	}

 	return 0;

}

巴特西

洛谷P1854 花店橱窗布置

最新文章

热门文章