Educational Codeforces Round 80 (CF - 1288C - Two Arrays)

传送门：点此跳转至题目

方法1： dp计数

状态转移方程：dp( i , j , k ) = sum[ dp( i - 1 , x , y ) ] , 1<=x<=j , k<=y<=n , x<=y；

dp( i , j , k ) 表示 在长度为 i 的数组，对于数组最后一个数字（即第i个） a[i] = j , b[i] = k 的总情况数；
其中，a数组是单调不递减的,b数组是单调不递增的，ai<=bi；

乍一看，这个转移方程的复杂度为 O(m * n ^ 4) ,但其实仔细品味 ，第 i 次的dp(i)值所求的区域和sum 是 第i - 1 次dp(i-1) 的一个矩阵 ，故可用二位前缀和优化，将dp(i) 作为 dp(i-1) 的二维前缀和，复杂度就变成了 O(m * n ^ 2) ;

dp[i][j][k]=dp[i-1][j][k]+dp[i][j-1][k]+dp[i][j][k+1]-dp[i][j-1][k+1];

当然还要注意 ai <= bi 的条件：

AC代码：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<cmath>
#include<functional>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
const int N=1e3+5;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const long double pi=acos(-1.0L);
#define ls (i<<1)
#define rs (i<<1|1)
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define mem(a,b) memset(a,b,sizeof(a))
LL read()
{
    LL x=0,t=1;
    char ch;
    while(!isdigit(ch=getchar())) if(ch=='-') t=-1;
    while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); }
    return x*t;
}
LL dp[15][N][N];
int main()
{
    int n=read(),m=read();
    for(int i=1;i<=n;i++)
        for(int j=n;j>=i;j--)
            dp[1][i][j]=1;
 
    for(int i=2;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
            for(int k=n;k>=j;k--){
            //该转移方程可用二维滚动数组优化空间复杂度
                dp[i][j][k]=dp[i-1][j][k]+dp[i][j-1][k]+dp[i][j][k+1]-dp[i][j-1][k+1];
                dp[i][j][k]%=mod;
           
            }
    }
    LL ans=0;
    for(int i=1;i<=n;i++)
        for(int j=n;j>=i;j--){
            ans+=dp[m][i][j];
            ans%=mod;
        }
 
    printf("%lld\n",ans);
    return 0;
}

方法二：构造+计数

将 a 数组 和 b数组的逆序数组连接，构成一个长度为 2 * m 的新数组，保证数组单调不递减，求可构造的总情况数。
问题转化后，就可以将二维前缀和转化成一维的前缀和了，复杂度O(n * m)；
代码

L dp[N];
int main()
{
    int n=read(),m=read();
    for(int i=1;i<=n;i++) dp[i]=1;
    m<<=1;
    for(int i=2;i<=m;i++)
        for(int j=1;j<=n;j++)
            dp[j]=(dp[j]+dp[j-1])%mod;
    LL ans=0;
    for(int i=1;i<=n;i++) ans=(ans+dp[i])%mod;
    printf("%lld\n",ans);
    return 0;
}

方法三：构造+组合数学

C( 2 * m , n + 2 * m - 1) ;
从n个数字里选m个数作排序（可选相同的，而能选的相同的数最多2*m个，且这个数在 1-n 种已经出现一次， 故 n + 2 * m -1 个）