题目链接:Click here~~
题意:
给两种颜色不同数量的方块,以等差数列的方式去摆放,要求每层颜色一致,设最高高度为 h,问有多少种高为 h 的摆法。
思路:
开始想到用 DP 的方法去解,但数据范围把我吓怕了,于是使劲去想贪心构造的方法,但智商明显不够用。
这题扔完一个多月了,今天查了下题解,其实还是 DP。
由 两种方块的总数量 的范围,可以估算出,理论最大层数不会超过 10^3。
由于摆放方块时的限制非常少,所以其实我们甚至不用关心上一层摆的是 R 还是 G,只需要关心剩下各多少颜色的方块可以用 。
首先想到 dp[i][j][k] 表示前 i 层,用 j 块红色,k 块绿色的方案数。
然后,k 这一维是可以约掉的,因为前两维 i 和 j 可以准确确定出 k 。
约掉后,i * j 的空间还是太大,所以还需要用滚动数组实现。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 2e5 + 5; const int mod = 1e9 + 7; int dp[2][N]; bool avalible[2][N]; int main() { int r, g; scanf("%d%d", &r, &g); if(r > g) { swap(r, g); } avalible[0][0] = true; dp[0][0] = 1; int cur = 1; bool can_get_next = true; int h = 0; for(int i = 1; can_get_next != false; ++i) { memset(avalible[cur], false, sizeof(avalible[cur])); memset(dp[cur], 0, sizeof(dp[cur])); can_get_next = false; h = i; const int &tot_used = h * (h + 1) / 2; for(int j = 0; j <= min(r, tot_used); ++j) { const int &red_used = j; const int &gre_used = tot_used - red_used; const int &cur_need = h; if(red_used >= cur_need && avalible[cur ^ 1][red_used - cur_need]) { (dp[cur][red_used] += dp[cur ^ 1][red_used - cur_need]) %= mod; avalible[cur][red_used] = true; can_get_next = true; } if(gre_used <= g && avalible[cur ^ 1][red_used]) { (dp[cur][red_used] += dp[cur ^ 1][red_used]) %= mod; avalible[cur][red_used] = true; can_get_next = true; } } cur ^= 1; } int ans = 0; for(int j = 0; j <= r; ++j) { (ans += dp[h & 1 ^ 1][j]) %= mod; } printf("%d\n", ans); return 0; }