传送门：点此跳转至题目
方法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
",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
",ans);
return 0;
}
方法三：构造+组合数学
C( 2 * m , n + 2 * m - 1) ;
从n个数字里选m个数作排序（可选相同的，而能选的相同的数最多2*m个，且这个数在 1-n 种已经出现一次， 故 n + 2 * m -1 个）