P1077 摆花

作者

[永遠の記憶 ~ Precious Memories]施工D15

2020.8.25
转载自luogu

P1077 摆花

Noip2012 T3

题目传送门

腹泻式更新.jpg
这同样也是那次考试的题目，我看到都傻了，这东西还能用 $dp$ 做？？

因为我也不是很会dp，所以下面有错的请指正。
按照惯例，每年普及的 $T3$ ，有极大可能是 $dfs$ 、$dp$ 或者记忆化搜索，所以我们得到结论，这道题模拟是必定不能 $AC$ 的。

题目中所要求的量是方案数,通过分析可知，方案数并不是一个最优解，也就是说，并不是全局最大值或者全局最小值，而是一个局部最大值的累加之和。

由以上思路，我们定义出一个二维数组 $dp[i][j]$ ，其中 $dp[i][j]$ 表示确定前 $i$ 种花，摆放 $j$ 盆后的最多的方案数。

并且不难推出状态转移方程： $dp_{i,j} = dp_{i,j} + \sum\limits_{k=0}^{min(j,a_i)}dp_{i-1,j-k}$

其中 $k$ 枚举当前种类花摆放的个数，保证比 $m$ （剩余花盆数量）和 $a_i$ （最多摆放数量）。
同时，为了防止数据在运算中溢出，我们在每次运算中使用模运算。

综合以上，我们可以写出代码：

#include <bits/stdc++.h>
using namespace std;

const int mod = 1000007;
int n, m;
int a[101];
int dp[101][101];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		dp[i][0] = 1;
	}
	for (int i = 1; i <= a[1]; ++i) {
		dp[1][i] = 1;
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			for (int k = 0; k <= a[i]; ++k) {
				dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % mod;
			}
		}
	}
	cout << dp[n][m] << endl;
	return 0;
}

头一次写 $dp$ 的题解这么顺畅，不过写之前这个代码我看了一下午才看懂。
果然还是没有写 $dp$ 的天赋啊.jpg
去写作业了，拜拜~

发表评论