[HDU4689]Derangement

https://zybuluo.com/ysner/note/1232641

题面

给出\(b_1,b_2,...,b_n\in\{−1,1\}\),求满足\((p_i−i)*b_i<0\)的\(\{1,2,...,n\}\)的排列\(p_i\)的数量。

\(n\leq20\)

解析

一开始并不知道这状态怎么设

设\(f[i][j]\)表示当前填到了第\(i\)个位置，有\(j\)个\(b_i>0\)（即\(+\)号）不满足。

则可顺利写出决策：

当前位置是\(+\)：

1、用当前的\(i\)填掉前面的一个空，有\(j\)种选择。

2、该位不填，留到后面用。
当前位置是\(-\)：（必须用掉）

1、用当前的\(i\)填掉前面的一个空，有\(j\)种选择。

2、替代前面一个\(+\)号，再从前面的\(+\)号中选一个填在这里，均有\(j\)种选择。

这种“延时\(DP\)”我似乎只会用它来计数。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#define re register

#define il inline

#define ll long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define fp(i,a,b) for(re int i=a;i<=b;i++)

#define fq(i,a,b) for(re int i=a;i>=b;i--)

using namespace std;

char s[25];

ll n,f[25][25];

il ll gi()

{

  re ll x=0,t=1;

  re char ch=getchar();

  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

  if(ch=='-') t=-1,ch=getchar();

  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

  return x*t;

}

int main()

{

  while(scanf("%s",s+1)!=EOF)

    {

      n=strlen(s+1);memset(f,0,sizeof(f));

      f[0][0]=1;

      fp(i,1,n)

	{

	  if(s[i]=='+')

	    fp(j,1,i)

	      f[i][j]+=f[i-1][j-1]+f[i-1][j]*j;

	  else

	    fp(j,0,i)

	    {

	      f[i][j]+=f[i-1][j]*j+f[i-1][j+1]*(j+1)*(j+1);

	    }

	}

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

    }

  return 0;

}

巴特西

[HDU4689]Derangement

https://zybuluo.com/ysner/note/1232641

题面

解析

最新文章

热门文章