526互联

P1854 花店橱窗布置

发布时间 2023-11-15 11:56:01作者: 加固文明幻景

P1854 花店橱窗布置

初始思路

  • 状态方程

    • \(F_{i, j}\) 为前 \(i\) 种花，装在前 \(j\) 个花瓶内的最大美学值。

  • 状态转移

    \[F_{i, j} = \max(F_{i, j}, F_{i - 1, k} + a_{i, j}) j \in [i, v - (f - i)], k \in [1, j) \]

其中 \(j\) 和 \(i\) 的范围推了好久。

一开始口胡了一个范围过了样例，然后爆零。

后面静下心来慢慢推，\(j\) 肯定必须要满足前面的花能装，后面的花也要装完的条件，根据这个推出 \(j\) 的范围，然后 \(k\) 肯定小于 \(j\)，因为后一种花必须装在前一种花的后一个花瓶内。

至此大框架是完成了，但是还有很多问题。

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;

int f, v;
int a[101][101]; 
int dp[101][101];
int ans[101], tag[101];
int maxx = 0;

int main()
{
	cin >> f >> v;
	for (int i = 1; i <= f; i++)
	{
		for (int j = 1; j <= v; j++)
		{
			cin >> a[i][j];
		}
	}
	for (int i = 1; i <= f; i++)
	{
		for (int j = i; j <= v; j++)
		{
			dp[i][j] = dp[i - 1][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];
					tag[j] = k; 
				}
			}
		}
	}
	int cnt = f, p;
	for (int i = f; i <= v; i++)
	{
		if (maxx < dp[f][i])
		{
			maxx = dp[f][i];
			p = i;
		}
	}
	cout << maxx << endl;
	for (int i = p; cnt != 0; i = tag[i], j--)
	{
		ans[cnt--] = i; 
	}
	for (int i = 1; i <= f; i++)
	{
		cout << ans[i] << " ";
	}

	return 0;
}

DEBUG

  • 跑数据发现，方案是错误的，答案是正确的。
    • 不能用一维数组记录二维DP的方案。
      • 因为一个 \(j\) 可能由多个不同的状态转移而来
    • 应用二维数组记录方案
  • 跑数据发现，答案可能是负数，那么初始值的设定都有问题
    • DP数组为 \(i = 1\) 时出了问题，本来想初始化解决但很麻烦
      • 干脆直接略过那一次 DP ,反正 \(i = 1\)时 DP 数组肯定是 \(a_{1,j}\)。
      • for (int i = 1; i <= v; i++) dp[1][i] = a[1][i];
    • 答案 maxx 要初始化为极小值而非 \(0\)

AC代码

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;

int f, v;
int a[101][101]; 
int dp[101][101];
int ans[101], tag[101][101];
int maxx = -0x7fffffff;

int main()
{
	cin >> f >> v;
	for (int i = 1; i <= f; i++)
	{
		for (int j = 1; j <= v; j++)
		{
			cin >> a[i][j];
		}
	}
	for (int i = 1; i <= v; i++)
	{
		dp[1][i] = a[1][i];
	}
	for (int i = 2; i <= f; i++)
	{
		for (int j = i; j <= v - (f - 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];
					tag[i][j] = k; 
				}
			}
		}
	}
	int cnt = f, p;
	for (int i = f; i <= v; i++)
	{
		if (maxx < dp[f][i])
		{
			maxx = dp[f][i];
			p = i;
		}
	}
	cout << maxx << endl;
	for (int i = p, j = f; cnt != 0; i = tag[j][i], j--)
	{
		ans[cnt--] = i; 
	}
	for (int i = 1; i <= f; i++)
	{
		cout << ans[i] << " ";
	}

	return 0;
}