Mountain Scenes

Descriptions

给你一个长度为n的丝带,一个宽w一个高h 的 格子,用丝带去填充格子,这填充后只需要满足至少有一列的丝带长度与其他格子不同即可。丝带可以不全部用上,格子可以不放丝带,只要有一列的丝带长度不同则这种放法就与其他方案不同。问一共有多少种放放法。

Sample Input1

25 5 5

Sample Output 1

7770

Sample Input 2

15 5 5

Sample Output 2

6050

Sample Input 3

10 10 1

Sample Output 3

1022

Sample Input 4

4 2 2

Sample Output 4

6

题目链接

https://vjudge.net/problem/Gym-101002F

dp[i][j]代表到第i列为止用了j米长的情况数,下一状态等于前一状态的各种情况的总和

代码中有几点要解释一下   tmp=n/w+1 求的是按宽绳子全用铺平,看能铺几层 再加上 0这一层

            h+1 求的是按高来铺绳子,能铺h+1层

            min(tmp,h+1) 求的是最终能铺几层

AC代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 10000+10
using namespace std;
ll n,w,h;
ll dp[][Maxn];
int main()
{
cin>>n>>w>>h;
MEM(dp,);
dp[][]=;
for(int i=; i<=w; i++)//枚举列
for(int j=; j<=n; j++)//枚举到前一列为止用了多少绳子
if(dp[i-][j])//前一次更新过才能更新下一个
{
for(int k=; k<=h; k++)//枚举这一列的高度
{
if(j+k>n)//高度超过总绳长就不行
break;
dp[i][j+k]=(dp[i][j+k]+dp[i-][j])%Mod;
}
}
ll tmp=n/w+;
ll ans=;
for(int i=;i<=n;i++)
ans=(ans+dp[w][i])%Mod;
cout<<(ans-min(tmp,h+)+Mod)%Mod<<endl;
return ;
}

最新文章

  1. 初识WebService
  2. Nodejs学习笔记(八)--- Node.js + Express 实现上传文件功能(felixge/node-formidable)
  3. linux下简单文本处理
  4. Eclipse插件安装
  5. Linux管道编程实例
  6. 图解slub
  7. C#经典面试题及答案
  8. jQuery 选择器demo练习
  9. bitnami-redmine邮件告警配置
  10. 10 -- 深入使用Spring -- 5... 实现任务的自动调度
  11. 尽量少嵌套无用的div;外部文件尽量使用link而不要使用用@import
  12. 铁乐学python_shelve模块详解
  13. PHP 中call_user_func相关函数的使用
  14. Unique Binary Search Trees,Unique Binary Search Trees2 生成二叉排序树
  15. Chrome Postman及Firefox Poster使用
  16. 《挑战程序设计竞赛》2.6 数学问题-辗转相除法 AOJ0005 POJ2429 1930(1)
  17. 触发显示和隐藏 div
  18. DNS的概念,用途,DNS查询的实现算法
  19. kuangbin专题16D(next求最小循环节)
  20. C#特性类的使用

热门文章

  1. linux-deployment
  2. 在Mac OSX下使用ssh建立隧道(在Windows下建立隧道可以使用putty,其间会用到ppk文件)
  3. hadoop 数据抽取
  4. cookie 和 session 区别
  5. Unity Shader 菲涅尔环境反射
  6. 【设计模式】行为型10中介者模式(Mediator Pattern)
  7. maven导入jar包于本地库中
  8. Linux下编译PHP常见错误及解决方法
  9. vSphere克隆虚机重启网卡报错
  10. eclipse中一个项目引用另一个项目,运行报:java.lang.NoClassDefFoundError