D. Red-Green Towers
 

There are r red and g green blocks for construction of the red-green tower. Red-green tower can be built following next rules:

  • Red-green tower is consisting of some number of levels;
  • Let the red-green tower consist of n levels, then the first level of this tower should consist of n blocks, second level — of n - 1 blocks, the third one — of n - 2 blocks, and so on — the last level of such tower should consist of the one block. In other words, each successive level should contain one block less than the previous one;
  • Each level of the red-green tower should contain blocks of the same color.

Let h be the maximum possible number of levels of red-green tower, that can be built out of r red and g green blocks meeting the rules above. The task is to determine how many different red-green towers having h levels can be built out of the available blocks.

Two red-green towers are considered different if there exists some level, that consists of red blocks in the one tower and consists of green blocks in the other tower.

You are to write a program that will find the number of different red-green towers of height h modulo 109 + 7.

Input

The only line of input contains two integers r and g, separated by a single space — the number of available red and green blocks respectively (0 ≤ r, g ≤ 2·105, r + g ≥ 1).

Output

Output the only integer — the number of different possible red-green towers of height h modulo 109 + 7.

Sample test(s)
input
4 6
output
2
 
Note

The image in the problem statement shows all possible red-green towers for the first sample.

题意:给你 r,g,分别表示红色,绿色方块的数目,现在如题图所示,叠方块:满足每一行都是同一种颜色

问你方案数是多少。

题解:  一眼dp

我们可以先想到:dp[i][j]表示 从底层叠到i层  红色方块用了j个的方案数 显然绿色用了(i)*(i+1)/2-j;

我们就能想到转移方程了很简单。

然后,你会发现这就是个背包,dp[894][200000]会爆内存,我们可以用滚动数组来 省掉一维,dp[j]表示修建了n层红色方块用j的方案数,我们必须处理处最少的j的第一种方案...........

///
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll;
#define mem(a) memset(a,0,sizeof(a))
#define inf 100000
inline ll read()
{
ll x=,f=;
char ch=getchar();
while(ch<''||ch>'')
{
if(ch=='-')f=-;
ch=getchar();
}
while(ch>=''&&ch<='')
{
x=x*+ch-'';
ch=getchar();
}
return x*f;
}
//****************************************
#define maxn 200000+5
int mod=;
int n;
ll dp[maxn],f[maxn];
int main(){ int a=read(),b=read();
for(int i=;;i--){
if((i*(i+)/)<=(a+b)){
n=i;break;
}
}int next=;
for(int i=;;i--){
if((i*(i+)/)<=(b)){
next=i;break;
}
}//cout<<n<<endl;
dp[]=;
// cout<<next<<endl;
for(int i=;i<=n;i++){
for(int j=;j<=a;j++){f[j]=dp[j];dp[j]=;if(j>(i*(i+)/))break;}
for(int j=;j<=a;j++){
if(((i-)*(i)/-j+i)<=b)
dp[j]=(dp[j]+f[j])%mod;
if(j-i>=)
dp[j]=(dp[j]+f[j-i])%mod;
if(j>(i*(i+)/))break;
}
}
int ans=;
for(int i=;i<=a;i++){
// cout<<dp[i]<<" "<<f[i]<<endl;
ans=(ans+dp[i])%mod;
}
printf("%d\n",ans);
return ;
}

代码

最新文章

  1. 封装Nvelocity的渲染方法
  2. iOS开发——高级技术&amp;GameCenter服务
  3. sell- 获取邮箱的后缀
  4. hibernate和mybatis
  5. 【转】linux内核调试技巧之一 dump_stack
  6. 写一个段落python代码推理list深浅
  7. C#实现的内存分页机制的一个实例
  8. 开涛spring3(2.2) - IoC 容器基本原理及其helloword
  9. Servlet基础(工作原理、生命周期)
  10. Nginx安装及配置
  11. k64 datasheet学习笔记21--Direct Memory Access Multiplexer (DMAMUX)
  12. Mybatis 传递多个参数
  13. 二进制样式的字符串与byte数组互转函数示例
  14. python自学第9天,装饰器
  15. CLOS网络架构与FATTREE胖树拓扑
  16. flask框架----蓝图
  17. 《Effective Java》学习笔记 —— 枚举、注解与方法
  18. Binary Tree ZigZag Level Order Traversal leetcode java
  19. Mysql命令行改动字段类型
  20. Mysql----数据备份、pymysql模块

热门文章

  1. 【译】x86程序员手册30-8.2 I/O指令
  2. python学习笔记(5)—— tuple 本质探究
  3. 搭建jQuery开发环境
  4. vim之vimrc配置文件
  5. 梦想iOS版CAD控件2018.11.07更新
  6. 08css、JS
  7. java学习日志---File实例:实现复制整个文件夹、解决listFiles()为null问题
  8. Qt 如何处理密集型耗时的事情
  9. 使用yolo3模型训练自己的数据集
  10. SpringSecurity 获取认证信息 和 认证实现