[DP记录]AT2370 [AGC013D] Piling Up

command_block · 2021-04-29 07:40:15 · 个人记录

题意 ： 一开始袋子中有 n 个黑白球，但不知道黑白色各有多少。

进行 m 次操作，每次先拿出一个球，再放入黑白球各一个，再拿出一个球。

将拿出的球按顺序排列，求形成的颜色序列有多少种。答案对 10^9+7 取模。

• 取出白白 ： 黑球个数增加一个， dp[i+1][j+1]{\texttt{ += }}dp[i][j]

• 取出黑白或白黑 ： 黑球个数不变， dp[i+1][j]{\texttt{ += }}2dp[i][j]

  特殊地，当 j=0 时，不能取黑白，当 j=n 时，不能取白黑。

现在考虑初始时黑球数目不定的情况。似乎只需要将 dp[0][0\sim n] 都置为 1 就好了？

这样会导致重复计数。我们将一个操作方案中袋中黑球的变化情况画成折线，平移后能重合的折线产生的颜色序列是相同的，但却被统计了多次。

于是，我们只统计接触过 x 轴的折线（即中途黑球个数曾为 0 的方案），这样就不会重复了。

多开一维 0/1 记录这个。

复杂度 O(n^2)。

#include<algorithm>
#include<cstdio>
#define MaxN 3050
using namespace std;
const int mod=1000000007;
int n,m,dp[MaxN][MaxN][2];
int main()
{
    scanf("%d%d",&n,&m);
    dp[0][0][1]=1;
    for (int j=1;j<=n;j++)
      dp[0][j][0]=1;
    for (int i=0;i<m;i++)
      for (int j=0;j<=n;j++){
        if (j>0){
          if (j==1)dp[i+1][j-1][1]=(dp[i+1][j-1][1]+dp[i][j][0])%mod;
          else dp[i+1][j-1][0]=(dp[i+1][j-1][0]+dp[i][j][0])%mod;
          dp[i+1][j-1][1]=(dp[i+1][j-1][1]+dp[i][j][1])%mod;
          if (j==1)dp[i+1][j][1]=(dp[i+1][j][1]+dp[i][j][0])%mod;
          else dp[i+1][j][0]=(dp[i+1][j][0]+dp[i][j][0])%mod;
          dp[i+1][j][1]=(dp[i+1][j][1]+dp[i][j][1])%mod;
      }
      if (j<n){
        dp[i+1][j+1][0]=(dp[i+1][j+1][0]+dp[i][j][0])%mod;
        dp[i+1][j+1][1]=(dp[i+1][j+1][1]+dp[i][j][1])%mod;
        dp[i+1][j][0]=(dp[i+1][j][0]+dp[i][j][0])%mod;
        dp[i+1][j][1]=(dp[i+1][j][1]+dp[i][j][1])%mod;
      }
    }
  int ans=0;
  for (int j=0;j<=n;j++)
    ans=(ans+dp[m][j][1])%mod;
  printf("%d",ans);
    return 0;
}