CF1288C Two Arrays

· · 题解

题目传送门

先考虑怎么计算单调不降序列的个数，计数当然要 dp。设 dp_{i,j} 表示长度为 i，最后一个数是 j 的不降序列个数。转移很显然：dp_{i,j}=\sum_{k=1}^j dp_{i-1,k}。

这有什么用呢？考虑一个非常妙的转换。

根据题意：

a_1\le a_2\le\dots\le a_{m-1}\le a_m b_1\ge b_2\ge\dots\ge b_{m-1}\ge b_m a_m\le b_m\le b_1

因此 a_1\le a_2\le\dots\le a_{m-1}\le a_m\le b_m\le b_{m-1}\le\dots\le b_2\le b_1

这时只要求长度为 2\times m 的不降序列个数即可。

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=30,M=1e3+10,mod=1e9+7;
int n,m,dp[N][M];
signed main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%d%d",&m,&n);n<<=1;
    for(int i=1;i<=m;i++)dp[0][i]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int k=1;k<=j;k++)
                dp[i][j]=(dp[i-1][k]+dp[i][j])%mod;
    printf("%d\n",dp[n][m]);
    system("pause");
    return 0;
}

record