Codeforces 478D Red-Green Towers:dp
2024-08-29 19:08:48
题目链接:http://codeforces.com/problemset/problem/478/D
题意:
给你r个红方块和g个绿方块,让你用这些方块堆一个塔。
最高层有1个方块,每往下一层块数+1,同时要保证每层中的方块都是同一种颜色。
如图:
问你在塔的高度最高的前提下,堆出塔的方案数。
题解:
假设塔最高能堆d层,则:
d*(d+1)/2 <= r+g
解得:
d = floor((-1+sqrt(1+8*(r+g)))/2)
并且d最大不超过900。
表示状态:
dp[i][j] = numbers
表示已经堆了最上面的i层,用了j个红方块,此时的方法数。
找出答案:
ans = ∑ dp[d][max(0,d*(d+1)/2-g) to r]
因为最终还要保证用了绿方块的个数 <= g,所以枚举i至少要从d*(d+1)/2-g开始。
如何转移:
dp[i][j] = dp[i-1][j] + dp[i-1][j-i]
从上往下数第i层可能全用绿色,或全用红色
边界条件:
dp[0][0] = 1
另外要用滚动数组,否则会MLE。
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_D 900
#define MAX_R 200005
#define MOD 1000000007
#define EPS 1e-5 using namespace std; int r,g,d;
int dp[][MAX_R]; int main()
{
cin>>r>>g;
d=floor((-1.0+sqrt(1.0+8.0*(r+g))+EPS)/2.0);
memset(dp,,sizeof(dp));
dp[][]=;
for(int i=;i<=d;i++)
{
for(int j=;j<=r;j++)
{
dp[i&][j]=dp[(i-)&][j];
if(j-i>=) dp[i&][j]+=dp[(i-)&][j-i];
dp[i&][j]%=MOD;
}
}
int ans=;
for(int i=max(,d*(d+)/-g);i<=r;i++)
{
ans=(ans+dp[d&][i])%MOD;
}
cout<<ans<<endl;
}
最新文章
- Timequest GUI
- Devexpress Ribbon
- Swift:属性观察器
- 图解Android - Binder 和 Service
- php敏感词过滤
- Oracle函数面试题
- BrnShop开源网上商城第六讲:扩展视图功能
- chrome浏览器当表单自动填充时,怎么去除浏览器自动添加的默认样式。
- (转) html块级元素和内联元素区别详解
- AS3开发必须掌握的内容
- netstat 查看连接数
- IOS学习1——IOS应用程序的生命周期及基本架构
- dedecms织梦网站图片集上传图片出现302错误图片提示怎么解决 已测
- 8.String StringBuffer StringBuilder
- macOS 上编译 Dynamips
- UE3多参数函数实现
- day11_python_1124
- Landsat8 卫星数据下载
- The Golden Age CodeForces - 813B (数学+枚举)
- Android NDK MediaCodec在ijkplayer中的实践
热门文章
- .net之GridView、DataList、DetailsView(一)
- iOS iPhoneX/iPhoneXS/iPhoneXR/iPhoneXS Max系列适配
- sersync简介与测试报告
- HBase概念及表格设计
- php党 强烈推荐TIPI:深入理解PHP内核
- iOS 企业版 安装失败 原因
- lua面向对象铺垫
- python 函数的进阶
- images have the “stationarity” property, which implies that features that are useful in one region are also likely to be useful for other regions.
- 错误解决Error configuring application listener of class org.springframework.web.util.Log4jConfigListener(转发)