分类 状压DP 下的文章

BZOJ 1087: [SCOI2005]互不侵犯King

Description在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上左下右上右下八个方向上附近的各一个格子,共8个格子。Input只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)Output方案数。Sample Input3 2Sample Output16 有 16 种Solution简单的状态压缩DP,设 DPi[k] 表示前 i 行放 j 个且最后一行的状态为 k,转移显然。别忘了开 long longCode#include <cstdio>- 阅读剩余部分 -

POJ 1185: 炮兵阵地

Description司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成,地图的每一格可能是山地(用"H" 表示),也可能是平原(用"P"表示),如下图。在每一格平原地形上最多可以布置一支炮兵部队(山地上不能够部署炮兵部队);一支炮兵部队在地图上的攻击范围如图中黑色区域所示: 如果在地图中的灰色所标识的平原上部署一支炮兵部队,则图中的黑色的网格表示它能够攻击到的区域:沿横向左右各两格,沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在,将军们规划如何部署炮兵部队,在防止误伤的前提下(保证任何两支炮兵- 阅读剩余部分 -

BZOJ 1688: [Usaco2005 Open]Disease Manangement 疾病管理

Description唉!一组D(1 .D <= 15)疾病(编号1 . D)在农场里运行。农夫约翰想要尽可能多的牛奶(1 <= N <= 1000)。如果挤奶的奶牛携带超过K(1 <= K <= D)不同的疾病,那么牛奶将被污染得太严重,必须完全丢弃。请帮助确定最大数量的奶牛而不需要丢弃牛奶。Input第一行:三个空格分隔的整数:N、D和K第2行。N+ 1:Line i+ 1 描述了牛i的疾病,列表中有一个或多个空格分隔的整数。第一个整数,d_i,是牛i病的计数;下一个d_i整数列举了实际的疾病。当然,如果d_i为0,列表是空的。Output- 阅读剩余部分 -

BZOJ 1725: [Usaco2006 Nov]Corn Fields牧场的安排

题目描述Farmer John新买了一块长方形的牧场,这块牧场被划分成M列N行(1<=M<=12; 1<=N<=12),每一格都是一块正方形的土地。FJ打算在牧场上的某几格土地里种上美味的草,供他的奶牛们享用。遗憾的是,有些土地相当的贫瘠,不能用来放牧。并且,奶牛们喜欢独占一块草地的感觉,于是FJ不会选择两块相邻的土地,也就是说,没有哪两块草地有公共边。当然,FJ还没有决定在哪些土地上种草。 作为一个好奇的农场主,FJ想知道,如果不考虑草地的总块数,那么,一共有多少种种植方案可供他选择。当然,把新的牧场荒废,不在任何土地上种草,也算一种方案。请你帮F- 阅读剩余部分 -