链接:https://codeforces.com/contest/1288/problem/C

C. Two Arrays

题意:给定一个数n和一个数m,让构建两个数组a和b满足条件,1.数组中所有元素的取值在1~n之间,a和b数组长度是m。2. a数组是单调不递减的,b数组是单调不递增 3. 任意的位置i,有a<=b

思路:可以组合数学做,也可以dp,以下为dp做法。首先如果把a、b两个数组合并成 a,a,a,.......a,b,b,b,b...........b,b,b会发现整个数列是单调不递减的,那么就可以dp做了,

dp[i][j]表示第i个位置可以放 大于等于 j 的方案数 ,那么转移方程就是 dp[i][j] = dp[i-1][j] + dp[i][j+1]

AC代码:

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const int maxm = ;
const int maxn = 1e3+;
const int mod = 1e9+;
ll dp[maxm*][maxn];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i = ;i<=n;i++) dp[][i] = ;
for(int i = ;i<=*m;i++){
for(int j = n;j>=;j--){
dp[i][j] = (dp[i][j+] + dp[i-][j])%mod;
}
}
ll ans = ;
for(int i = ;i<=n;i++){
ans = (ans+dp[*m][i])%mod;
}
printf("%d",ans);
return ;
}
05-22 06:11
查看更多