[jzoj 5230] 队伍统计 {状态压缩DP}

news/2024/11/14 0:30:56/

题目

Description
现在有n个人要排成一列,编号为1->n 。但由于一些不明原因的关系,人与人之间可能存在一些矛盾关系,具体有m条矛盾关系(u,v),表示编号为u的人想要排在编号为v的人前面。要使得队伍和谐,最多不能违背k条矛盾关系(即不能有超过k条矛盾关系(u,v),满足最后v排在了u前面)。问有多少合法的排列。答案对10^9+7取模。

Input
输入文件名为count.in。
第一行包括三个整数n,m,k。
接下来m行,每行两个整数u,v,描述一个矛盾关系(u,v)。
保证不存在两对矛盾关系(u,v),(x,y),使得u=x且v=y 。

Output
输出文件名为count.out。
输出包括一行表示合法的排列数。


解题思路

f i , j f_{i,j} fi,j 表示 i i i表示状态, j j j表示违背了的条件个数。
我们可以枚举队头,算出插入队头前的状态 l a s t last last和将插入队头后会违背的条件个数 f l a g flag flag(即判断状态里有多少个一)。
可以这么处理:

int find(int x){int xx=0; while (x) x-=(x&-x),xx++; return xx;}

动态转移方程为: f i , j + = f l a s t , j − f l a g f_{i,j}+=f_{last,j-flag} fi,j+=flast,jflag


代码

#include<cstdio>
#include<algorithm>
#define rep(i,x,y) for (register int i=x;i<=y;i++)
#define fre(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout)
#define N 21
using namespace std;
const int pe=1e9+7; 
int n,m,k,f[1<<N][N],ans,a[N],cnt,last,flag; 
int find(int x){int xx=0; while (x) x-=(x&-x),xx++; return xx;}
int main(){//fre(count);scanf("%d%d%d",&n,&m,&k); int x,y; cnt=1<<n; f[0][0]=1; rep(i,1,m) scanf("%d%d",&x,&y),a[y-1]|=1<<(x-1); rep(i,0,cnt-1) rep(j,0,n-1) if ((i>j)&1){flag=find((last=(i^(1<<j)))&a[j]); rep(q,flag,k) (f[i][q]+=f[last][q-flag])%=pe; } rep(i,0,k) (ans+=f[cnt-1][i])%=pe; printf("%d",ans); 
}    

http://www.ppmy.cn/news/346231.html

相关文章

jzoj5230. 队伍统计 (B组——Day9)

jzoj5230. 队伍统计 &#xff08;B组——Day9&#xff09; 题目 Description 现在有n个人要排成一列&#xff0c;编号为1->n 。但由于一些不明原因的关系&#xff0c;人与人之间可能存在一些矛盾关系&#xff0c;具体有m条矛盾关系(u,v),表示编号为u的人想要排在编号为v的…

hdu 5230 ZCC loves hacking

刚开始滚动数组错了 #include <iostream> #include <algorithm> #include <cstring> #include <functional> #include <cmath> using namespace std; typedef long long ll; const int MAXN 100005; const int MAXNUM 320; const ll INF 0x3f…

Jzoj5230 队伍统计

现在有n个人要排成一列&#xff0c;编号为1->n 。但由于一些不明原因的关系&#xff0c;人与人之间可能存在一些矛盾关系&#xff0c;具体有m条矛盾关系(u,v),表示编号为u的人想要排在编号为v的人前面。要使得队伍和谐&#xff0c;最多不能违背k条矛盾关系&#xff08;即不能…

在TaiShan200 server 2180 昆鹏920 5230裸服务器上安装 ubuntu18.04

最近客户那边要搭建一个开源异构服务器云平台。 一共有两种不同构架的服务器&#xff0c;一种是x86构架的&#xff0c;另外一种就是arm构架的&#xff08;本文涉及的鲲鹏服务器当时使用时&#xff0c;只有一块1T的SATA硬盘&#xff09;。 在这个网站 http://old-releases.ubun…

hdu 5230 整数划分 dp

题目&#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid5230 题意&#xff1a;给定n,c,l,r。求有多少种方法从1~n-1选取任意k数每个数的权重为其下标&#xff0c;使得这些数字之和加上c之后在l,r范围内。 题解&#xff1a;第一反应是计数01包&#xff0c;但是范围给定的n…

【JZOJ5230】队伍统计【状压DP】

题目大意&#xff1a; 题目链接&#xff1a;https://jzoj.net/senior/#main/show/5230 现在有 n n n个人要排成一列&#xff0c;编号为 1 ∼ n 1\sim n 1∼n 。但由于一些不明原因的关系&#xff0c;人与人之间可能存在一些矛盾关系&#xff0c;具体有 m m m条矛盾关系 ( u , …

hdu5230

bc41第三题&#xff1a; 由 1 &#xff5e; n-1 这 n-1 个数组成 l - c 到 r - c 闭区间内的数共有多少种组合方法&#xff1b; 据称本来应该也比较简单吧&#xff0c;xiaoxin说了个五边形数&#xff0c;然后纷纷找了五边形数的模板&#xff0c;虽然并没有来得及AC&#xff0c;…

hdu 5230

ZCC loves hacking 题目描述&#xff1a; 其实就是给了n~100000&#xff0c;c&#xff0c;l&#xff0c;r&#xff0c;其中C≤L≤R 题解&#xff1a; 所有情况数&#xff0c;刚开始一定会想dp【i】【j】用到数i达到和j的背包的算法&#xff0c;但是发现太大了。而且没有很好…