双色塔

#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;
}

/**
 * 
 * @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();
    }
}

#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;



	}