现在有红,绿两种颜色的石头,现在我们需要用这两种石头搭建一个塔,塔需要满足如下三个条件:
1. 第 1 层应该包含1块石头,第2层应该包含两块,第 i 层需要包含 i 块石头。
2. 同一层的石头应该是同一个颜色(红或绿)。
3. 塔的层数尽可能多。 问在满足上面三个条件的前提下,有多少种不同的建造塔的方案,当塔中任意一个对应位置的石头颜色不同,我们就认为这两个方案不相同。石头可以不用完。
数据范围:红绿颜色石头数量满足 ,
输入仅包含两个正整数,分别表示红和绿砖块的数量a,b。
输出和仅包含一个正整数,表示不同的方案数对1000000007取模的结果。
4 6
2
从底到顶颜色可以是 红、绿、红、绿 或 绿、绿、绿、红
#include <bits/stdc++.h> using namespace std; #define INIT() ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); const int MOD = 1000000007; const int N = 200007; //滚动数组 //dp[level&1][j]表示前level层放j个石头 //(个数较少那个颜色的石头,假定为绿色) //这样在两种颜色石头不均匀时 //可以优化复杂度 //dp数组全部更新的最坏复杂度为 //O(level*min(a,b)) //(level可计算出最大约为400sqrt(5)) //所以差不多是O(10^8)的复杂度 int dp[2][N + 5]; void solve(int a, int b) { if(a==0||b==0) { cout<<1<<endl; return; } memset(dp, 0, sizeof(dp)); int level = sqrt(2 * (a + b)); if (a > b) swap(a, b); dp[1][0] = dp[1][1] = 1; int sum = 1, lower, upper; int cur, last; for (int i = 2; i <= level; i++) { sum += i; //前i层最多要放的绿石个数(最多sum个,但不能超过绿石总个数a) int tmp_upper = min(sum, a); //前i层最少要放的绿石个数 //最坏情况,前i层将b个红石放完(sum-b>0),那么前i层至少放sum-b个绿石 //若sum-b<0,说明前i层最少可以不放红石,即dp[i][j]中j从0开始更新 //综上,j的更新范围下界为max(sum - b, 0) int tmp_lower = max(sum - b, 0); //下界大于上界,说明红石放完,绿石总数量也不够放下一层了,那么就是最高层了 //停止更新 if (tmp_lower > tmp_upper) break; upper = tmp_upper; lower = tmp_lower; cur = i & 1; last = !cur; //dp[i-1][j]表示第i层放红石 // dp[i-1][j-i]表示第i层放绿石(那么前i层至少i个绿石(即j>=i)) //转移方程:dp[i][j] = dp[i-1][j] + dp[i-1][j-i](j>=i) //前i层的绿石少于j,说明第i层只可能放了红石 //dp[i][j] = dp[i-1][j](j<i) for (int j = lower; j < i; j++) dp[cur][j] = dp[last][j]; for (int j = i; j <= upper; j++) { dp[cur][j] = (dp[last][j] + dp[last][j - i]) % MOD; } } int ans = 0; for (int j = lower; j <= upper; j++) { ans = (ans + dp[cur][j]) % MOD; } cout << ans << endl; } int main() { INIT() int a, b; while (cin >> a >> b) { solve(a, b); } return 0; }
#include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; int main(){ int a,b; cin>>a>>b; if(a==0 || b==0){ cout<<1<<endl; return 0; } if(a>b) swap(a,b); int dp[300001], t=1, l, r, s=0; memset(dp,0,sizeof(dp)); dp[0] = dp[1] = 1; for(int i=2;i<=sqrt(2*(a+b));i++){ t += i; int q = min(t, a); int p = max(t-b, 0); if(p>q) break; r = q; l = p; for(int j=r;j>=i+1;j--) dp[j] = (dp[j]+dp[j-i])%MOD; dp[i]++; } for(int i=l;i<=r;i++) s = (s+dp[i])%MOD; cout<<s<<endl; return 0; }
#include <iostream>#include <algorithm>using namespace std;const int MOD = 1000000007;const int N = 200001;int dp[N]; //使用单个数组取代原来的双数组,内存可以减少一半,速度稍慢(197ms, 1140KB)int solve(int a,int b) {int level = sqrt(2 * (a + b));if(a > b) swap(a, b);dp[0] = dp[1] = 1;int sum = 1, lower, upper;for(int i = 2; i <= level; i++) {sum += i;int tmp_upper = min(sum, a);int tmp_lower = max(sum - b, 0);if(tmp_lower > tmp_upper) break;upper = tmp_upper;lower = tmp_lower;for(int j = upper; j >= i + 1; --j) { //从最大往最小更新(从数组的右侧向左更新)dp[j] = (dp[j] + dp[j - i]) % MOD;}dp[i]++;}int ans = 0; //算法的总体原理都是相同的:假设红色的石头数量最少 //那么先用全部的绿色石头和尽可能少的红色石头(lower)组成尽可能多的层数(level), //将红色石头的使用数量逐渐提高至红色石头总数(upper), //lower到upper的每种可能的总和就是所有情况for(int j = lower; j <= upper; j++) {ans = (ans + dp[j]) % MOD;}return ans;}