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