【题解】HDU4689 Derangement(有技巧的计数DP)

呵呵没告诉我多测组数，然后\(n\le 20,7000\mathrm{ms}\)我写了个状压上去T了

题目大意：

要你求错排的方案数，但要求\(i\)位上的数比\(i\)大/小。大小关系用正负号告诉你，读入一个字符串。

\(O(n2^n)\)

设\(dp(s)\)表示已经放了\(|s|\)个数进去，放的数占满了\(s\)中的位置的方案数

转移太显然直接贴代码

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define DE(s) cerr<<(#s)<<"="<<(s)<<endl;

#define lowbit(x) ((x)&-(x))

using namespace std;  typedef long long ll;

inline int qr(){

      register int ret=0,f=0;

      register char c=getchar();

      while(!isdigit(c))f|=c==45,c=getchar();

      while(isdigit(c)) ret=ret*10+c-48,c=getchar();

      return f?-ret:ret;

}

const int maxn=20;

int n,U;

ll dp[1<<maxn];

char c[maxn];

int main(){

      while(~scanf("%s",c)){

	    n=strlen(c);

	    dp[0]=1;

	    U=(1<<n)-1;

	    for(int t=1;t<=U;++t){

		  dp[t]=0;

		  int cnt=0;

		  for(int g=t;g;g-=lowbit(g)) ++cnt;

		  for(int i=0,g=t;i<n&&g;++i){

			if(g>>i&1){

			      if(c[i]=='+'&&cnt>i+1) dp[t]+=dp[t^(1<<i)];

			      if(c[i]=='-'&&cnt<i+1) dp[t]+=dp[t^(1<<i)];

			      g^=1<<i;

			}

		  }

	    }

	    printf("%lld\n",dp[U]);

      }

      return 0;

}

过不了别想了

\(O(n^2)\)

考虑+号是一个后缀性的匹配，-号是一个前缀型的匹配。也就是说我们不可能直接把数给选好，要在后面再进行选择。这启发我可以设这样的状态：

\(dp(i,j)\)表示已经考虑前\(i\)个符号，但是需要从后面拉来\(j\)个\(>i\)数来凑齐前面的\(“+”\)。

当前是负号：

当前位置上的数拿来匹配前面的+

\[\]

\[
\]

\[\]

\[
\]
当前位置上的数拿来匹配前面一个+

\[\]

\[
\]

\[\]

\[

\]

//@winlere

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define DE(s) cerr<<(#s)<<"="<<(s)<<endl

#define lowbit(x) ((x)&-(x))

using namespace std;  typedef long long ll;

inline int qr(){

      register int ret=0,f=0;

      register char c=getchar();

      while(!isdigit(c))f|=c==45,c=getchar();

      while(isdigit(c)) ret=ret*10+c-48,c=getchar();

      return f?-ret:ret;

}

const int maxn=25;

int n,U;

ll dp[maxn][maxn];

char c[maxn];

int main(){

      while(~scanf("%s",c+1)){

	    n=strlen(c+1);

	    memset(dp,0,sizeof dp);

	    dp[0][0]=1;

	    int cnt_minus=0,cnt_plus=0;

	    for(int t=1;t<=n;++t){

		  if(c[t]=='-') {

			for(int i=0;i<=cnt_plus;++i)

			      dp[t][i]=dp[t-1][i+1]*(t-1-(cnt_plus-(i+1))-cnt_minus)*(i+1ll)*(i+1<=cnt_plus)+dp[t-1][i]*(t-1-(cnt_plus-i)-cnt_minus);

			++cnt_minus;

		  }

		  else {

			for(int i=0;i<=cnt_plus+1;++i){

			      if(i) dp[t][i]+=dp[t-1][i-1];

			      dp[t][i]+=dp[t-1][i]*i;

			}

			++cnt_plus;

		  }

	    }

	    printf("%lld\n",dp[n][0]);

      }

      return 0;

}

巴特西

【题解】HDU4689 Derangement(有技巧的计数DP)

【题解】HDU4689 Derangement(有技巧的计数DP)

\(O(n2^n)\)

\(O(n^2)\)

最新文章

热门文章