首页 > 试题广场 > 双色塔
[编程题]双色塔

现在有红,绿两种颜色的石头,现在我们需要用这两种石头搭建一个塔,塔需要满足如下三个条件:  1. 第1层应该包含1块石头,第2层应该包含两块,第 i 层需要包含 i 块石头。  2. 同一层的石头应该是同一个颜色(红或绿)。  3. 塔的层数尽可能多。  问在满足上面三个条件的前提下,有多少种不同的建造塔的方案,当塔中任意一个对应位置的石头颜色不同,我们就认为这两个方案不相同。石头可以不用完。


输入描述:
输入仅包含两个正整数,分别表示红和绿砖块的数量a,b(0<=a,b<=2*10^5,a+b>=1)。


输出描述:
输出和仅包含一个正整数,表示不同的方案数对1000000007取模的结果。
示例1

输入

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;
}
发表于 2019-06-10 11:14:14 回复(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;
}
状态转移方程:q(n,m)   在1--n中相加等于m的所有可能

编辑于 2019-07-07 16:40:35 回复(1)
在此粘贴下管哥的代码给大家参考下
import java.util.*;

/**
 * 
 * @author DRG
 * DRG NB
 *
 */
public class Main2 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int G = in.nextInt();
        int R = in.nextInt();
        int min = Math.min(R, G);
        int max = Math.max(R, G);
        R = min;
        G = max;
        int level = 1, sum = 0;
        /**
         * level 为最大层数
         */
        while (sum <= R + G) {
            level++;
            sum += level;
        }
        /**
         * array[i][j]表示前i层有j个绿色宝石的方案数
         * 那么可以得出递推式 array[i][j]=array[i-1][j-i]+array[i-1][j];
         * 针对第i层来说,如果第i层放置绿色宝石,那么前i-1层就只能放j-i个绿色宝石,所以为array[i-1][j-i]
         * 如果第i层不放置绿色宝石,而放红色宝石,那么前i-1层就放j个绿色宝石,为array[i-1][j]
         * 所以没有必要保存所有的状态,只需要保存上一层和当前层的状态即可
         */
        int[][] array = new int[2][G + 1];
        int answer = 0;
        if (G > 0) {
            array[1][1] = 1;
            answer++;
        }
        if (R > 0) {
            array[1][0] = 1;
            answer++;
        }
        int total = 1;
        int result;
        /**
         * total是前lev层所需要的石头总数量,不分颜***r />          */
        for (int lev = 2; lev < level; lev++) {
            total += lev;
            result = 0;
            /**
             * one代表当前层
             * two代表上一层
             */
            int one = lev % 2;
            int two = (lev - 1) % 2;
            /**
             * 遍历在当前层放置的绿色宝石的数量
             */
            for (int i = 0; i <= total && i <= G; i++) {
                array[one][i] = 0;
                /**
                 * 当放在第lev层是绿色宝石的时候,那么
                 * array[one][i]+=array[two][i-lev]
                 * 因为本来就只有i颗绿色宝石,你在lev层放置了lev颗之后,那么前lev-1层只能放置i-lev颗绿色宝石
                 * 而前lev-1层只能放置i-lev颗绿色宝石为array[two][i-lev]
                 */
                if (i >= lev && R >= total - i) {
                    array[one][i] += array[two][i - lev];
                    if (array[one][i] >= 1000000007) {
                        array[one][i] %= 1000000007;
                    }

                }
                /**
                 * 当放在第lev层是红色宝石的时候,那么
                 * array[one][i]+=array[two][i]
                 * 因为本来就只有i颗绿色宝石,你在lev层没有放置绿色宝石,那么就是说在lev-1层放置了lev颗绿色宝石
                 * 而前lev-1层只能放置lev颗绿色宝石为array[two][lev]
                 */
                if (total - i <= R) {
                    array[one][i] += array[two][i];
                    if (array[one][i] >= 1000000007) {
                        array[one][i] %= 1000000007;
                    }
                }
                /**
                 * 因为one代表的是当前层,所以把它累加起来即可得出最终结果
                 */
                if (array[one][i] != 0) {
                    result += array[one][i];
                    if (result >= 1000000007) {
                        result %= 1000000007;
                    }
                }
            }
            answer=result;
        }
        System.out.println(answer);
        in.close();
    }
}
 
发表于 2019-05-28 19:39:15 回复(2)