[jzoj5230]队伍统计

发表于 2017-08-25   |   分类于 动态规划


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。
输出包括一行表示合法的排列数。

Sample Input

输入1:
4 2 1
1 3
4 2

输入2:
10 12 3
2 6
6 10
1 7
4 1
6 1
2 4
7 6
1 4
10 4
10 9
5 9
8 10

Sample Output

输出1:
18

输出2:
123120

Data Constraint

对于30%的数据,n<=10
对于60%的数据,n<=15
对应100%的数据,n,k<=20,m<=n*(n-1),保证矛盾关系不重复。

状压dp:
dpsta表示sta状态下k个矛盾的方案数,

 dp[sta|2^j-1][k+num[sta&book[j]]]+=dp[sta][k]
#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
const int modd=1000000007,_maxn=(1<<20)+50;
int getint(){
    int ans=0;
    char ch=getchar();
    while(ch<'0' || ch>'9')
        ch=getchar();
    while(ch>='0' && ch<='9'){
        ans=ans*10+ch-'0';
        ch=getchar();
    }
    return ans;
}
int n,m,k,book[25],num[_maxn];
ll dp[_maxn][21];
void init(){
    dp[0][0]=1;
    int cnt,temp;
    for(int i=0;i<(1<<n);i++){
        temp=i;
        cnt=0;
        while(temp){
            cnt++;
            temp=temp&(temp-1);
        }
        num[i]=cnt;
    //     cout<<i<<' '<<num[i]<<endl;
    }
}
int main(){
    freopen("count.in","r",stdin);
    freopen("count.out","w",stdout);
    ios::sync_with_stdio(false);
    n=getint();m=getint();k=getint();
    int x,y;
    init();
    for(int i=1;i<=m;i++){
        x=getint();y=getint();
        book[x]=book[x]|(1<<y-1);//x want to queue in front of y
    }
    int t;
    for(int i=0;i<(1<<n);i++){
        for(int j=1;j<=n;j++){
            if(i&(1<<j-1))
                continue;
            t=num[book[j]&i];
            for(int l=0;l+t<=k;l++){
                dp[i|(1<<j-1)][t+l]=(dp[i|(1<<j-1)][t+l]+dp[i][l])%modd;
            //      cout<<dp[i][t]<<endl;
            }
        }
    }
    ll ans=0;
    for(int i=0;i<=k;i++)
        ans=(ans+dp[(1<<n)-1][i])%modd;
    cout<<ans<<endl;
    return 0;
}

已有 2 条评论


  1. VMice

    233,过来膜下。

    VMice October 30th, 2017 at 11:15 pm回复
    1. helloworld

      233,代码都是抄的,没啥可膜

      helloworld November 7th, 2017 at 09:20 pm回复

发表新评论

© 2017 Powered by Typecho & Theme Quark