Problem Description
N个人围成一圈在讨论大扫除的事情,需要选出K个人。但是每个人与他距离为2的人存在矛盾,所以这K个人中任意两个人的距离不能为2,他们想知道共有多少种方法。
Input
第一行包含一个数T(T<=100),表示测试数据的个数。
接下来每行有两个数N,K,N表示人数,K表示需要的人数(1<=N<=1000,1<=K<=N)。
Output
输出满足题意的方案数,方案数很大,所以请输出方案数mod 1,000,000,007 后的结果。
Sample Input
4 2
8 3
Sample Output
16
Source
FOJ有奖月赛-2015年10月
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define ls i<<1
#define rs ls | 1
#define mid ((ll+rr)>>1)
#define pii pair<int,int>
#define MP make_pair
typedef long long LL;
typedef unsigned long long ULL;
const long long INF = 1e18+1LL;
const double pi = acos(-1.0);
const int N = 1e3+, M = 1e6+, mod = 1e9+,inf = 2e9; void update(int x,int& y) {
y += x;
if(y > mod) y -= mod;
}
int T,dp[][][N][N],f[][][N][N];//前i个人选j人,前两人状态
void init() {
dp[][][][] = ;
dp[][][][] = ;
dp[][][][] = ;
dp[][][][] = ;
dp[][][][] = ;
dp[][][][] = ;
dp[][][][] = ; dp[][][][] = ; dp[][][][] = ;
dp[][][][] = ;
dp[][][][] = ; dp[][][][] = ;
dp[][][][] = ;
dp[][][][] = ; dp[][][][] = ; for(int i = ; i < ; ++i) {
for(int j = ; j < ; ++j) {
for(int k = ; k <= ; ++k) {
for(int h = ; h <= k; ++h)
f[i][j][k][h] = dp[i][j][k][h];
}
}
}
f[][][][] = ;
f[][][][] = ;
for(int k = ; k < ; ++k) {
for(int h = ; h < ; ++h) {
for(int i = ; i <= ; ++i) {
for(int j = ; j <= i; ++j) {
//不选, i-1选
if(i >= ) {
if(!k && j >= ) update(f[k][h][i-][j-],dp[k][h][i][j]);
if(!k && j >= )
if(i >= )update(f[k][h][i-][j-],dp[k][h][i][j]);
}
else {
if(!k && j >= ) update(f[k][h][i-][j-],dp[k][h][i][j]);
} //i不选,i-1不选
update(f[k][h][i-][j],dp[k][h][i][j]);
//i位置选,i-1不选
if(!h&&j>=)update(f[k][h][i-][j-],dp[k][h][i][j]); //i位置选,i-1选
if(!k&&!h&&j>=)
update(f[k][h][i-][j-],dp[k][h][i][j]); update(f[k][h][i-][j],f[k][h][i][j]);
if(i>=&&j>=)update(f[k][h][i-][j-],f[k][h][i][j]);
if(i>=&&j>=)update(f[k][h][i-][j-],f[k][h][i][j]);
}
}
}
}
}
int main() {
init();
scanf("%d",&T);
while(T--) {
int k,n;
scanf("%d%d",&n,&k);
int ans = ;
for(int i = ; i < ; ++i) {
for(int j = ; j < ; ++j) {
update(dp[i][j][n][k],ans);
}
}
printf("%d\n",ans);
}
return ;
}
FZUOJ Problem 2200 cleaning DP的更多相关文章
-
FZU Problem 2200 cleaning dp
Problem Description N个人围成一圈在讨论大扫除的事情,需要选出K个人.但是每个人与他距离为2的人存在矛盾,所以这K个人中任意两个人的距离不能为2,他们想知道共有多少种方法. Inp ...
-
ZOJ Problem Set - 3822Domination(DP)
ZOJ Problem Set - 3822Domination(DP) problemCode=3822">题目链接 题目大意: 给你一个n * m的棋盘,每天都在棋盘上面放一颗棋子 ...
-
fzuoj Problem 2129 子序列个数
http://acm.fzu.edu.cn/problem.php?pid=2129 Problem 2129 子序列个数 Accept: 162 Submit: 491Time Limit: ...
-
hdu4976 A simple greedy problem. (贪心+DP)
http://acm.hdu.edu.cn/showproblem.php?pid=4976 2014 Multi-University Training Contest 10 1006 A simp ...
-
fzuoj Problem 2179 chriswho
http://acm.fzu.edu.cn/problem.php?pid=2179 Problem 2179 chriswho Accept: 57 Submit: 136 Time Limi ...
-
fzuoj Problem 2177 ytaaa
http://acm.fzu.edu.cn/problem.php?pid=2177 Problem 2177 ytaaa Accept: 113 Submit: 265Time Limit: ...
-
【HDU 5233】Tree chain problem (树形DP+树剖+线段树|树状数组)最大权不相交树链集
[题目] Tree chain problem Problem Description Coco has a tree, whose vertices are conveniently labeled ...
-
Western Subregional of NEERC, Minsk, Wednesday, November 4, 2015 Problem G. k-palindrome dp
Problem G. k-palindrome 题目连接: http://opentrains.snarknews.info/~ejudge/team.cgi?SID=c75360ed7f2c7022 ...
-
D. Easy Problem(简单DP)
题目链接:http://codeforces.com/contest/1096/problem/D 题目大意:给你一个字符串,然后再给你去掉每个字符串的每个字符的花费,然后问你使得字符中不再存在har ...
随机推荐
-
linux split 命令 将一个大的文件拆分成若干小文件
. 以行数拆分 -l 参数: 原始文件 拆分后文件名前缀 例:以50行对文件进行拆分 big.txt small_ 拆分后会生成 small_aa small_ab small_ac ... . 以大 ...
-
windows 8.1 试用感受:蛋疼感大幅降低
众所周知windows 8 的最大使用感受就是蛋疼. 无论是微软MVP,还是我这样的万年不悔微软小白鼠,普通用户,小白用户,或多或少的都对这款操作系统感到蛋疼. 槽点太多,以至于大家都懒得批判了.好在 ...
-
Redis学习——SDS字符串源码分析
0. 前言 这里对Redis底层字符串的实现分析,但是看完其实现还没有完整的一个概念,即不太清楚作者为什么要这样子设计,只能窥知一点,需要看完redis如何使用再回头来体会,有不足之处还望告知. 涉及 ...
-
docker开发_在basic image的基础上创建自定义的image
方法一:docker commit 1. 跑一个basic image,docker新建了一个容器 root@ubuntu:/home/thm/docker/test# docker run -i - ...
-
iOS利用单例实现不同界面间的数据传输
首先写一个单例类,继承NSObject check.h文件中 @property(strong ,nonatomic) UITable * Table; @property(strong ,nonit ...
-
Phantomjs安装
环境:Centos 6.5 介绍:PhantomJS 是一个基于 WebKit 的服务器端 JavaScript API.它全面支持web而不需浏览器支持,其快速,原生支持各种Web标准: DOM 处 ...
-
使用Excel快速发送大量的电子邮件
使用Excel快速发送大量的电子邮件.两个步骤: 1. 准备发送数据: a.) 打开Excel,新Book1.xlsx b.) 填写以下内容. 第一列:接受者,第二列:邮件标题,第三列:文,第四列:附 ...
-
Java编程思想非主流知识点
1. Java中的多态性理解(注意与C++区分) Java中除了static方法和final方法(private方法本质上属于final方法,因为不能被子类访问)之外,其它所有的方法都是动态绑定,这意 ...
-
How to build mscorlib.dll with visual studio
Recently, Microsoft Corportation has released a new look for .NET Reference Source. And you may find ...
-
Java集合总结系列2:Collection接口
Collection 接口是 Java 集合类的一个根接口,Java 在 Collection 接口中定义了许多通用的数据操作类方法以及判断类方法. 通过查看 API 文档或源码的方式,我们可以了解到 ...