一道DP

时间:2021-11-27 03:27:07

也是校赛学长出的一道题~想穿了很简单。。但我还是听了学长讲才明白。

观察力有待提高。

Problem D: YaoBIG’s extra homework
Time Limit
Memory Limit
1 s
128 MB
Description
One day, a teacher assigned this extra homework to students of UCAS:
"What’s the number of the solution that an n n ladder is covered by exactly n rectangles? Note
that every two rectangles cannot overlap and the rectangles cannot reach out of the ladder."(The "Note"
section gives you an example of the "ladder".)
While YaoBIG was awkward, he still wanted the extra points, so he asked you to help him.
Input
The input contains zero or more test cases and the first line of the input gives the number T of test
cases. For each test case:
There is only one line with an integer n.
Output
For each test case, output the number of the solution that an n n ladder is covered by exactly n
rectangles, which is described above.
Notice that the answer might be too large, so you should output the answer modulo 1000000007.
Limits
0 <=T <=1 000
1 <=n <=1000
Sample input and output
Sample Input Sample Output
1
4
14
Note
The diagram explaining the case where n = 4 is shown below:

一道DP

大致复盘了一下应该怎么想。

从求n阶阶梯形由n个矩形填满的种类这个问题本身我们大致能嗅到一点DP的味道,并且同时比较容易发现搜索保证最后恰好是n个填满相当困难。

于是找一下有没有最优子结构。

关键在于一个矩形不可能填满两个棱角。所以每个棱角都必然由不同的矩形填充,然后考虑左上角的那个格子由某个矩形填充,左上角的格子和一个棱角格子由一个矩形占据,然后问题就被划分成了两个同理的子问题。

另外有1000个cases,但是只用算一遍然后对每个case输出答案即可。

 #include<cstdio>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define p 1000000007;
using namespace std;
const int MAXN=;
long long int dp[MAXN];
int main()
{
// freopen("in.txt","r",stdin);
int T;
scanf("%d",&T);
int n;
dp[]=;dp[]=;
rep(i,,)
{
rep(j,,i)
{
dp[i]+=dp[i-j]*dp[j-];
dp[i]%=p;
}
}
rep(i,,T)
{
scanf("%d",&n);
printf("%lld\n",dp[n]);
}
return ;
}

一道DP的更多相关文章

  1. 值得一做》关于一道DP&plus;SPFA的题 BZOJ1003 &lpar;BZOJ第一页计划&rpar; &lpar;normal-&rpar;

    这是一道数据范围和评测时间水的可怕的题,只是思路有点难想,BUT假如你的思路清晰,完全了解怎么该做,那就算你写一个反LLL和反SLE都能A,如此水的一道题,你不心动吗? 下面贴出题目 Descript ...

  2. Kickstart Round D 2017 problem A sightseeing 一道DP

    这是现场完整做出来的唯一一道题Orz..而且还调了很久的bug.还是太弱了. Problem When you travel, you like to spend time sightseeing i ...

  3. 62&period; Unique Paths&lpar;中等,我自己解出的第一道 DP 题&Hat;&Hat;&rpar;

    A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The ...

  4. 一道dp&lbrack;不太好写&rsqb;

    http://acm.csu.edu.cn:20080/csuoj/problemset/problem?pid=2281 Description An arithmetic progression ...

  5. nyoj16矩形嵌套(第一道dp关于dag的题目)

    http://acm.nyist.net/JudgeOnline/problem.php?pid=16 题意:有n个矩形,每个矩形可以用a,b来描述,表示长和宽.矩形X(a,b)可以嵌套在矩形Y(c, ...

  6. 2018微软实习笔试一道dp题目总结

    题意大概是说在一维数轴上起点和终点的距离是d,现在我们要从起点走到终点.每走一个单位长度消耗一个单位能量,初始时有K单位能量.同时在起点和终点之间分布一些加油站a1,a2,...an,给你加油站数量. ...

  7. USACO 6&period;1 Postal Vans(一道神奇的dp)

    Postal Vans ACM South Pacific Region -- 2003 Tiring of their idyllic fields, the cows have moved to ...

  8. 洛谷 P1466 集合 Subset Sums Label:DP

    题目描述 对于从1到N (1 <= N <= 39) 的连续整数集合,能划分成两个子集合,且保证每个集合的数字和是相等的.举个例子,如果N=3,对于{1,2,3}能划分成两个子集合,每个子 ...

  9. 【63测试20161111】【BFS】【DP】【字符串】

    第一题: tractor 题目描述 农场上有N(1 <= N <= 50,000)堆草,放在不同的地点上.FJ有一辆拖拉机,也在农场上.拖拉机和草堆都表示为二维平面上的整数坐标,坐标值在1 ...

随机推荐

  1. java 打包jar文件以在没有安装JDK或JRE的机子上运行

    前言: java号称“一次编译,到处运行”,但这有个前提,那就是你的机子上得安装java环境.对于开发人员或其他一些比较懂计算机的人来说这没什么,但是对于一些不懂计算机的人来说这会很麻烦,他们更希望的 ...

  2. SVN系列操作(一)

    SVN是什么? SVN是Subversion的简称,是一个开放源代码的版本控制系统,常用于软件开发项目中,实现代码.文档等的历史版本保存.共享和权限管理. 进入SVN本地目录,第一步操作就是updat ...

  3. &lpar;2&rpar;编译安装lamp三部曲之mysql-技术流ken

    简介 采用yum安装lamp简单,快捷,在工作中也得到了普遍应用.但是如果我们需要某些特定模块功能,以及制定安装位置等,就需要用到编译安装了,接下来将编译安装lamp之mysql. mysql的简介网 ...

  4. Ubuntu系统监控indicator-sysmonitor

    参考: http://www.cnblogs.com/EasonJim/p/7130171.html 安装indicator-sysmonitor sudo add-apt-repository pp ...

  5. nginx cookie 丢失问题

  6. Oracle 数据库、实例、用户、表空间、表之间的关系

    数据库: Oracle数据库是数据的物理存储.这就包括(数据文件ORA或者DBF.控制文件.联机日志.参数文件).其实oracle数据库的概念和其它数据库不一样,这里的数据库是一个操作系统只有一个库. ...

  7. 2017&period;7&period;12 Python的6种内建序列及操作

    数据结构是通过某种方式(例如对元素进行编号)组织在一起的数据元素的集合,这些数据元素可以是数字或者字符,甚至可以是其他数据结构. 在Python中,最基本的数据结构是序列(sequence).序列中的 ...

  8. UITextField使用的一些细节

    UITextField使用的一些细节 这篇博文是我自己使用UITextField的一些总结,并没有太多营养,并会持续更新. 2014.9.15 ---------------------------- ...

  9. Mac Sublime Text3快捷键

    下载地址http://www.sublimetext.com/3 一.安装Package Control 按Ctrl + ` 调出console,粘贴下列安装代码到底部命令行并回车: import u ...

  10. java实现遍历一个字符串的每一个字母(总结)

    基础:牢记字符串操作的各种方法: ​​​ ​ String s = "aaaljlfeakdsflkjsadjaefdsafhaasdasd"; // 出现次数 int num = ...