[Ceoi2016]kangaroo(bzoj4934)(神级DP)

2019/08/30 21:46
阅读数 209

传送门

这种DP是打死我也想不到的

学习自这篇神级博客

题目抽象一下就是

所以选出的排列根据p来排序一定是这种形态:

也就是很多博客里说的M型。

我们把一条边叫做一条链,也就是相邻两个数构成的即为一条链。(s,t是不算做链的

我们的dp就是去维护这样一个形态。

我们考虑从小到大往排列里放数,对于一个“山峰”,其左右两边的数一定在它之前就放过了(因为比它小)。

那么对于这一个数(要求不是s也不是t。因为s或t一定是起点/终点,而不是中间的一个),它可以去合并两条链,也可以自己单独作为一个新链。

如果这个数是s或者t的话,可以选择新开一个链或是作为某一条链的起点/终点。

定义f[i][j]为走了i步,现在有j跳链的方案数

结果即为f[n-1][0]

#include<bits/stdc++.h> 
#define LL long long
#define N 2003
#define mod 1000000007
using namespace std;
int read()
{
    int f=1,x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x*f;
}
LL f[N][N];//
int main()
{
    int n=read(),s=read(),t=read();
    f[0][0]=1;
    for(int i=1;i<n;++i)
      for(int j=0;j<i;++j) 
      {
          if(!f[i-1][j])continue;
          if(i!=s&&i!=t)
          {
              f[i][j+1]=(f[i][j+1]+f[i-1][j])%mod;//新开一条链
            if(j)f[i][j-1]=(f[i][j-1]+(f[i-1][j]*j%mod*(((j-1)+(i>s)+(i>t))%mod))%mod)%mod;//j*(j-1)+j*(i>s)+j*(i>t)
            //考虑上S和T,如果他们已经在之前被操作了,那么S所在的链头可以作为被合并的前半部分,方案数+j,
            //同理T可以在后半部分,方案数+j
        }
        else
        {
            f[i][j]=(f[i][j]+f[i-1][j])%mod;//新开一条链,但s、t不算在链里
            if(j)f[i][j-1]=(f[i][j-1]+f[i-1][j]*j%mod)%mod;
        }
      } 
    printf("%lld\n",f[n-1][0]);
}
/*
*/
View Code
展开阅读全文
*j
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部