FZUOJ Problem 2200 cleaning DP

时间:2022-08-26 10:23:10
Problem 2200 cleaning

FZUOJ Problem 2200 cleaning DP Problem Description

N个人围成一圈在讨论大扫除的事情,需要选出K个人。但是每个人与他距离为2的人存在矛盾,所以这K个人中任意两个人的距离不能为2,他们想知道共有多少种方法。

FZUOJ Problem 2200 cleaning DP Input

第一行包含一个数T(T<=100),表示测试数据的个数。

接下来每行有两个数N,K,N表示人数,K表示需要的人数(1<=N<=1000,1<=K<=N)。

FZUOJ Problem 2200 cleaning DP Output

输出满足题意的方案数,方案数很大,所以请输出方案数mod 1,000,000,007 后的结果。

FZUOJ Problem 2200 cleaning DP Sample Input

2
4 2
8 3

FZUOJ Problem 2200 cleaning DP Sample Output

4
16

FZUOJ Problem 2200 cleaning DP Source

FOJ有奖月赛-2015年10月

 
 
题解:
  设定 f[k][h] [i][j] 表示在不考虑环的清形下第一,二位置上的选择状态为k,h下,前i个选了j个人的方案数
    dp[k][h][i][j], 表示在考虑环的清形下第一,二位置上的选择状态为k,h下,前i个选了j个人的方案数
  那么对于f数组的递推,当前第i位置选与不选,i-1位置选与不选有
        f[k][h] = f[k][h][ii-1][j] +f[k][h][i-3][j-1] + f[k][h][i-4][j-2];
  对于dp数组转移同理就是拿f数组来更新
  具体看代码
#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的更多相关文章

  1. FZU Problem 2200 cleaning dp

    Problem Description N个人围成一圈在讨论大扫除的事情,需要选出K个人.但是每个人与他距离为2的人存在矛盾,所以这K个人中任意两个人的距离不能为2,他们想知道共有多少种方法. Inp ...

  2. ZOJ Problem Set - 3822Domination&lpar;DP&rpar;

    ZOJ Problem Set - 3822Domination(DP) problemCode=3822">题目链接 题目大意: 给你一个n * m的棋盘,每天都在棋盘上面放一颗棋子 ...

  3. fzuoj Problem 2129 子序列个数

    http://acm.fzu.edu.cn/problem.php?pid=2129 Problem 2129 子序列个数 Accept: 162    Submit: 491Time Limit: ...

  4. hdu4976 A simple greedy problem&period; (贪心&plus;DP)

    http://acm.hdu.edu.cn/showproblem.php?pid=4976 2014 Multi-University Training Contest 10 1006 A simp ...

  5. fzuoj Problem 2179 chriswho

    http://acm.fzu.edu.cn/problem.php?pid=2179 Problem 2179 chriswho Accept: 57    Submit: 136 Time Limi ...

  6. fzuoj Problem 2177 ytaaa

    http://acm.fzu.edu.cn/problem.php?pid=2177 Problem 2177 ytaaa Accept: 113    Submit: 265Time Limit: ...

  7. 【HDU 5233】Tree chain problem (树形DP&plus;树剖&plus;线段树&vert;树状数组)最大权不相交树链集

    [题目] Tree chain problem Problem Description Coco has a tree, whose vertices are conveniently labeled ...

  8. Western Subregional of NEERC&comma; Minsk&comma; Wednesday&comma; November 4&comma; 2015 Problem G&period; k-palindrome dp

    Problem G. k-palindrome 题目连接: http://opentrains.snarknews.info/~ejudge/team.cgi?SID=c75360ed7f2c7022 ...

  9. D&period; Easy Problem(简单DP)

    题目链接:http://codeforces.com/contest/1096/problem/D 题目大意:给你一个字符串,然后再给你去掉每个字符串的每个字符的花费,然后问你使得字符中不再存在har ...

随机推荐

  1. linux split 命令 将一个大的文件拆分成若干小文件

    . 以行数拆分 -l 参数: 原始文件 拆分后文件名前缀 例:以50行对文件进行拆分 big.txt small_ 拆分后会生成 small_aa small_ab small_ac ... . 以大 ...

  2. windows 8&period;1 试用感受:蛋疼感大幅降低

    众所周知windows 8 的最大使用感受就是蛋疼. 无论是微软MVP,还是我这样的万年不悔微软小白鼠,普通用户,小白用户,或多或少的都对这款操作系统感到蛋疼. 槽点太多,以至于大家都懒得批判了.好在 ...

  3. Redis学习——SDS字符串源码分析

    0. 前言 这里对Redis底层字符串的实现分析,但是看完其实现还没有完整的一个概念,即不太清楚作者为什么要这样子设计,只能窥知一点,需要看完redis如何使用再回头来体会,有不足之处还望告知. 涉及 ...

  4. docker开发&lowbar;在basic image的基础上创建自定义的image

    方法一:docker commit 1. 跑一个basic image,docker新建了一个容器 root@ubuntu:/home/thm/docker/test# docker run -i - ...

  5. iOS利用单例实现不同界面间的数据传输

    首先写一个单例类,继承NSObject check.h文件中 @property(strong ,nonatomic) UITable * Table; @property(strong ,nonit ...

  6. Phantomjs安装

    环境:Centos 6.5 介绍:PhantomJS 是一个基于 WebKit 的服务器端 JavaScript API.它全面支持web而不需浏览器支持,其快速,原生支持各种Web标准: DOM 处 ...

  7. 使用Excel快速发送大量的电子邮件

    使用Excel快速发送大量的电子邮件.两个步骤: 1. 准备发送数据: a.) 打开Excel,新Book1.xlsx b.) 填写以下内容. 第一列:接受者,第二列:邮件标题,第三列:文,第四列:附 ...

  8. Java编程思想非主流知识点

    1. Java中的多态性理解(注意与C++区分) Java中除了static方法和final方法(private方法本质上属于final方法,因为不能被子类访问)之外,其它所有的方法都是动态绑定,这意 ...

  9. How to build mscorlib&period;dll with visual studio

    Recently, Microsoft Corportation has released a new look for .NET Reference Source. And you may find ...

  10. Java集合总结系列2:Collection接口

    Collection 接口是 Java 集合类的一个根接口,Java 在 Collection 接口中定义了许多通用的数据操作类方法以及判断类方法. 通过查看 API 文档或源码的方式,我们可以了解到 ...