【HDU4689】Derangement（动态规划）

题面

给定一个\(+-\)组成的字符串，长度为\(n\)。

如果第\(i\)位是\(+\)，那么\(p_i>i\)，否则\(p_i<i\)

求满足上述条件的\([1,n]\)的排列个数。

题解

如果所有数都满足\(p_i<i\)，那么就是。

考虑如何暴力，我们可以直接大力容斥。

枚举一部分的\(+\)，强制将其变为没有任何限制，那么方案数还是上面\(RabbitNumbering\)那题，最后容斥计算即可。

但是这样子复杂度吃不下。

换种方式考虑。

如果我们从左往右依次填数，设\(f[i][j]\)表示当前填到了第\(i\)个位置，有\(j\)个\(+\)不满足。

假设当前位置是\(+\)，考虑如何转移

第一种是用当前的\(i\)填掉前面的一个\(+\)，这样一定能够满足。

或者让他填掉后面随便一个\(-\)号。

如果当前位置是一个\(-\)的话，我们必须要填掉，

因为前面空出来了\(j\)个\(+\)，所以有\(j\)个数可以用来填这个\(-\)，组合算一下。

那么，当前的这个\(i\)的抉择和前面一样，所以大力转移一下就好了。

忽然发现我的代码是这道题所有提交记录里面最短的？？？

#include
    
     #include
     
      #define ll long longll f[22][22];char ch[22];int n;int main(){    while(scanf("%s",ch+1)!=EOF)    {        n=strlen(ch+1);memset(f,0,sizeof(f));f[0][0]=1;        for(int i=1;i<=n;++i)            if(ch[i]=='+')                for(int j=1;j<=i;++j)f[i][j]=f[i-1][j-1]+f[i-1][j]*j;            else                for(int j=0;j<=i;++j)f[i][j]=f[i-1][j+1]*(j+1)*(j+1)+f[i-1][j]*j;        printf("%lld\n",f[n][0]);    }}