[HDU4689]Derangement

计数 DP

题面

给出$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;
}