首页 > 代码库 > CF273（D2）D DP
CF273（D2）D DP
【题意】：
给出N个绿色砖头和M个红色砖头，要堆成尽量高的如下规律的建筑，其中每一行只能用一种颜色。
问有多少种堆的方法。
【知识点】：
DP 滚动数组
【题解】：
在代码中，DP[i]代表用了i个红积木所对应的堆积种类。
REP(i, h) for(int j = N - i; j >= 0; j--) dp[i + j] = (dp[i + j] + dp[j]) % MOD;
第一层循环代表积木条的长度从小到大地放，第二层进行滚动更新。
【代码】：
#include <map>#include <set>#include <cmath>#include <ctime>#include <queue>#include <stack>#include <cstdio>#include <string>#include <vector>#include <cstring>#include <sstream>#include <iostream>#include <algorithm>#include <bitset>#include <climits>using namespace std;#define wh while#define inf (int)(~0u/2)#define FOR(i, n) for(int i = 0; i < n; i++)#define FOR1(i, n) for(int i = 1; i < n; i++)#define FOR2(i, n) for(int i = 0; i <= n; i++)#define REP(i,n) for(int i = 1; i <= n; i++)#define FORI(it,n) for(typeof(n.begin()) it = n.begin(); it != n.end(); it++)#define sf scanf#define pf printf#define frs first#define sec second#define psh push_back#define mkp make_pair#define PB(x) push_back(x)#define MP(x, y) make_pair(x, y)#define clr(abc,z) memset(abc,z,sizeof(abc))#define lt(v) v << 1#define rt(v) v << 1 | 1//#define mid ((l + r) >> 1)#define lson l, mid, v << 1#define rson mid + 1, r, v << 1 | 1#define fre freopen("1.txt", "r", stdin)typedef long long LL;typedef long double LD;int N, M;const int maxn = 2e5 + 100;const int MOD = 1000000007;int dp[maxn];int main() { sf("%d%d", &N, &M); int h; for(h = 1; h * (h + 1) / 2 <= (N + M); h++); h--; dp[0] = 1; REP(i, h) for(int j = N - i; j >= 0; j--) dp[i + j] = (dp[i + j] + dp[j]) % MOD; h = (h + 1) * h / 2; int ans; ans = 0; for(int j = 0; j <= N; j++) if(h - j <= M) ans = (ans + dp[j]) % MOD; pf("%d\n", ans);}
CF273（D2）D DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。