题目描述
小方有w个白色立方体和b个黑色立方体,现在小方想把它们堆成一个立方体塔。
一座高度为h的立方体塔,最底层有h个立方体,每往上一层,所需立方体减一,直到最高层只需要一个立方体。
为了让这座塔看起来美观,小方希望,每一层都只能用一种颜色的立方体。
小方希望把这座塔叠的尽可能高,因此他想知道塔的最大高度是多少,以及这个高度的立方体塔能有几种。
两种立方体塔,当且仅当至少有一层的颜色是不同的,则被认为是不同的。
输入格式
共一行,包含两个整数w和b。
输出格式
共一行,包含两个整数h和c,分别表示最高塔的高度以及此高度塔的种类数。
因为种类数可能较多,请将c对109+7取模后的值输出。
数据范围
0≤w,b≤105
样例
1 1
输出样例
1 2
算法1
(动态规划) $O(n^2)$
当不考虑w和b的不同时,h为满足( 1 + h ) * h / 2 <= w + b 的最大值
当考虑w和b的不同时,h同样为( 1 + h ) * h / 2 <= w + b 的最大值
证明:
可以将题目转换为:
是否能够使用1 ~ h的h个数,组合成 1 ~ ( h + 1 ) * h / 2的任意值
可以使用数学归纳法证明
求出h后,可以将题意转换为对于值val,使用1~h能够组成val的方式,就是典型的0-1背包问题
dp[ i ][ j ] 表示前i个数形成j的方案数
dp[ i ][ j ] = dp[ i - 1 ][ j ] + dp[ i - 1 ][ j - i ];
可以将二维优化为一维
dp[ j ] = dp[ j ] + dp[ j - i ]
注意:
j要从大到小枚举: 不然的话dp[ j - i ]对应于二维的dp[ i ][ j - i ]
C++ 代码
//二维
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
ll w, b, h;
ll dp[ 1000 ][ 100100 ];
int main()
{
cin >> w >> b;
h = 1000;
while( ( 1 + h ) * h / 2 > w + b ) h --;
dp[ 0 ][ 0 ] = 1;
ll goal = 0;
for( int i = 1; i <= h; i ++ )
for( int j = 0; j <= 100000; j ++ )
{
dp[ i ][ j ] = dp[ i - 1 ][ j ];
if( j >= i ) dp[ i ][ j ] = ( dp[ i ][ j ] + dp[ i ][ j - i ] ) % mod;
}
auto l = max( 0LL, ( 1 + h ) * h / 2 - b );
auto r = min( w, ( 1 + h ) * h / 2 );
for( auto i = l; i <= r; i ++ ) goal = ( goal + dp[ h ][ i ] ) % mod;
cout << h << " " << goal << endl;
return 0;
}
C++ 代码
//一维
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;
ll w, b, h;
ll dp[ 100100 ];
int main()
{
cin >> w >> b;
h = 1000;
while( ( 1 + h ) * h / 2 > w + b ) h --;
dp[ 0 ] = 1;
ll goal = 0;
for( int i = 1; i <= h; i ++ )
for( int j= 100000; j >= 0; j -- )
{
if( j >= i ) dp[ j ] = ( dp[ j ] + dp[ j - i ] ) % mod;
}
auto l = max( 0LL, ( 1 + h ) * h / 2 - b );
auto r = min( w, ( 1 + h ) * h / 2 );
for( auto i = l; i <= r; i ++ ) goal = ( goal + dp[ i ] ) % mod;
cout << h << " " << goal << endl;
return 0;
}