hdu 4301 dp
2024-08-29 14:58:54
Divide Chocolate
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1632 Accepted Submission(s): 765
Problem Description
It is well known that claire likes dessert very much, especially chocolate. But as a girl she also focuses on the intake of calories each day. To satisfy both of the two desires, claire makes a decision that each chocolate should be divided into several parts, and each time she will enjoy only one part of the chocolate. Obviously clever claire can easily accomplish the division, but she is curious about how many ways there are to divide the chocolate.
To simplify this problem, the chocolate can be seen as a rectangular contains n*2 grids (see above). And for a legal division plan, each part contains one or more grids that are connected. We say two grids are connected only if they share an edge with each other or they are both connected with a third grid that belongs to the same part. And please note, because of the amazing craft, each grid is different with others, so symmetrical division methods should be seen as different.
To simplify this problem, the chocolate can be seen as a rectangular contains n*2 grids (see above). And for a legal division plan, each part contains one or more grids that are connected. We say two grids are connected only if they share an edge with each other or they are both connected with a third grid that belongs to the same part. And please note, because of the amazing craft, each grid is different with others, so symmetrical division methods should be seen as different.
Input
First line of the input contains one integer indicates the number of test cases. For each case, there is a single line containing two integers n (1<=n<=1000) and k (1<=k<=2*n).n denotes the size of the chocolate and k denotes the number of parts claire wants to divide it into.
Output
For each case please print the answer (the number of different ways to divide the chocolate) module 100000007 in a single line.�
Sample Input
2
2 1
5 2
2 1
5 2
Sample Output
1
45
45
题目大意:给你一块2*n的巧克力,求把它切成k块的切法。
#include<iostream>
#include<cstdio>
using namespace std; const int M=;
int d[][][]={};
//i表示第i列,j表示分成j个,k表示最后一列的两种状态
//0表示最后一列分成一块,1表示分成两块 void init()
{
int i,j;
d[][][]=;d[][][]=;
for(i=;i<=;i++)
{
for(j=;j<=*i;j++)
{
d[i][j][]=(d[i-][j][]+*d[i-][j][]+d[i-][j-][]+d[i-][j-][])%M;
d[i][j][]=(d[i-][j][]+*d[i-][j-][]+*d[i-][j-][]+d[i-][j-][]+d[i-][j-][])%M;
}
}
}
int main()
{
int n,k,t;
init();
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&k);
printf("%d\n",(d[n][k][]+d[n][k][])%M);
}
return ;
}
最新文章
- CXF发布restful WebService的入门例子(客户端)
- 20 个超酷的 HTML5/CSS3 应用及源码
- MVVM模式的一个小例子
- 《University Calculus》-chape6-定积分的应用-求体积
- 基于laravel4.2的相关架构设计
- bootstrap data
- pcl1.7.2_vs2013_x64工程配置
- 安卓CTS官方文档之兼容性测试套件简介
- HDU 5795 A Simple Nim(SG打表找规律)
- Infix expression 计算 without &#39;(&#39; and &#39;)&#39;
- 关于pthread_create未定义的引用的奇葩解决
- LINQ TO XML初步了解
- 香港科技大学的VINS_MONO初试
- SpringMVC常用配置(二),最简洁的配置实现文件上传
- Django 基础二(View和urls)
- python全栈开发中级班全程笔记(第二模块)第一部分:文件处理
- chmod 755 是李鬼(转)
- Nest.js 管道
- eclipse显示代码行数
- 【Ansible 文档】提示、推荐、注意事项