程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [STOI2014]舞伴(dp),stoi2014舞伴dp

[STOI2014]舞伴(dp),stoi2014舞伴dp

編輯:C++入門知識

[STOI2014]舞伴(dp),stoi2014舞伴dp


STOI是汕頭OI...無聊翻到了去年的比賽題目,就寫然後自己測了一下。其實我很想吐槽為什麼題目名是perm,perm好像和舞伴完全無關..

dp(x,s)=∑dp(x-1,s-{i}))(0<=i<n,i∈s,i號女生和x號男生是朋友),dp(x,s)表示前x個男生已和女生配對,已配對女生用集合s表示。邊界:第0號男生和第i號女生(0<=i<n),若是朋友則 dp(0,{i})=1;否則dp(0,{i})=0.計算過程中邊算邊mod,最後輸出就OK了。

----------------------------------------------------------------------------

#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define rep(i,r) for(int i=0;i<r;i++)#define clr(x,c) memset(x,c,sizeof(x))using namespace std;const int maxn=20+5;int mod,n;int ok[maxn][maxn];int d[maxn][1<<20];int dp(int x,int s) {    int &ans=d[x][s];    if(ans>=0) return ans;    ans=0;    rep(i,n) if(ok[x][i] && (s & (1<<i)))        (ans+=dp(x-1,s^(1<<i)))%=mod;    return ans;}int main(){    freopen("perm.in","r",stdin);    freopen("perm.out","w",stdout);            clr(ok,0); clr(d,-1);    cin>>n>>mod;    rep(i,n) rep(j,n) scanf("%d",&ok[i][j]);    rep(i,n)        if(ok[0][i]) d[0][1<<i]=1;        else d[0][1<<i]=0;    cout<<dp(n-1,(1<<n)-1)<<endl;        return 0;}

------------------------------------------------------------------------------------
 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved