程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> BZOJ 2302 HAOI2011 Problem c 動態規劃

BZOJ 2302 HAOI2011 Problem c 動態規劃

編輯:C++入門知識

BZOJ 2302 HAOI2011 Problem c 動態規劃


題目大意:給定n個人和n個位置,要求生成一個序列ai,然後第1...n個人依次走到第a1...n個位置,如果那個位置已經有人了就走到下一個位置,直到找到一個空位,坐下。如果找完第n個座位還是沒有找到就稱這個序列不合法
現在已經確定了一些ai,求合法序列的數量

一個序列合法等價於編號≤i的人至少有i
然後就可以DP辣。。。
fi,j表示編號≤i的人有j個的方案數,cnti表示確定編號為i的人的個數,sumi表示編號可以≤i的人的個數
那麼有
fi,j=∑j−i+1k=cntifi−1,j−k∗Ck−cntisumi−cnti−(j−k)
那個組合數表示現在有sumi個人,cnti個人已經確定必須選,j−k個人已經選完了,在剩下的人中選出k−cnti個人使其編號為i
時間復雜度O(Tn3)
少打個回車調了一晚上……我真是老了啊……

#include 
#include 
#include 
#include 
#define M 330
using namespace std;
int n,m,p;
int cnt[M],sum[M];
long long C[M][M],f[M][M];
void Initialize()
{
    int i,j;
    memset(cnt,0,sizeof cnt);
    memset(C,0,sizeof C);
    memset(f,0,sizeof f);
    for(i=0;i<=n;i++)
        for(C[i][0]=1,j=1;j<=i;j++)
            C[i][j]=(C[i-1][j]+C[i-1][j-1])%p;
}
int main()
{
    int T,i,j,k,x;
    for(cin>>T;T;T--)
    {
        cin>>n>>m>>p;
        sum[0]=n-m;
        Initialize();
        for(i=1;i<=m;i++)
            scanf(%*d%d,&x),cnt[x]++;
        for(i=1;i<=n;i++)
        {
            sum[i]=sum[i-1]+cnt[i];
            if(sum[i]=i;j--)
                for(k=j-i+1;k>=cnt[i];k--)
                    (f[i][j]+=f[i-1][j-k]*C[sum[i]-j+k-cnt[i]][k-cnt[i]])%=p;
        printf(YES %d
,(int)f[n][n]);
    }
    return 0;
}

 

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