补充:这题我写复杂了, 想看简单解法指路打卡代码第一名0x3f的代码
这题一开始写了个sb记搜, 时间复杂度炸了, 然后仔细盯着数据范围算了一下
发现n = 1000, m = 10, o(n * n * m) 正好是1e7的时间, 基本就笃定了这题是一个双重循环n嵌套一层循环m的题
然后发现了一个很重要的性质, 如果一个数对(a[i], b[i])满足 a[i] <= b[i]
那在 j = 1 ~ i-1 的情况下, 一定都满足 a[j] <= b[j], 不相信的可以画图推一下
然后这题就可以变成一个简单dp了, 确定两个序列a, b, 判断他们在 各自递增递减的情况下, 有多少合法情况
定义状态, $f[ i ][ 0 / 1 ][j]$ 表示 以i为结尾的, 0表示a数组(递增) , 1表示b数组(递减), j表示第j层 (一共m层, 从前往后递推)
然后可以发现, $f[i][0][j]$ 和 $f[i][1][j]$ 的递推是独立的 , 我们可以根据枚举倒数第二位的数字来递推状态, 代码如下
for(int i = 2; i <= m; i ++ ){ //从第二层开始枚举的原因是, 第一层直接初始化就行
for(int j = 1; j <= n; j ++ ){
for(int k = 1; k <= j; k ++ ){
f[j][0][i] = (f[j][0][i] + f[k][0][i - 1]) % MOD; //0是a, 1是b
}
for(int k = n; k >= j; k -- ){
f[j][1][i] = (f[j][1][i] + f[k][1][i - 1]) % MOD;
}
}
}
最后根据乘法原理, 枚举最后一层的合法状态就行了
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= i; j ++ ){
ans = (ans + f[i][1][m] * f[j][0][m]) % MOD;
}
}
完整代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010, MOD = 1e9 + 7;
LL f[N][2][15];
int n, m;
int main()
{
scanf("%d%d", &n, &m);
LL ans = 0;
for(int i = 1; i <= n; i ++ )
f[i][0][1] = f[i][1][1] = 1;
for(int i = 2; i <= m; i ++ ){
for(int j = 1; j <= n; j ++ ){
for(int k = 1; k <= j; k ++ ){
f[j][0][i] = (f[j][0][i] + f[k][0][i - 1]) % MOD; //0是a, 1是b
}
for(int k = n; k >= j; k -- ){
f[j][1][i] = (f[j][1][i] + f[k][1][i - 1]) % MOD;
}
}
}
for(int i = 1; i <= n; i ++ ){
for(int j = 1; j <= i; j ++ ){
ans = (ans + f[i][1][m] * f[j][0][m]) % MOD;
}
}
printf("%lld", ans);
return 0;
}
看了榜上其他大佬的代码.... 感觉自己像弱智, 为什么他们只用一行
hhh但是你的清晰
我的dp比你的还复杂,看到大佬的嘛我觉得自己弱爆了