Educational Codeforces Round 80(C.Two Arrays)思维+DP

原题连接:https://codeforces.com/contest/1288/problem/C

比赛的时候没想起来,当时以为要用组合数学,没推出算式(第二天发现A题未用long long被hack掉了。。。难受)

给n、m 要求构造两个数组a、b,满足:

1.数组长度为m,数组元素在1-n范围内

2.ai<=bi

3.a数组非降序

4.b数组非升序

问有多少种构造方法,对1e9+7取模

所以总的长度为2*m

将a的末尾与b的末尾连接(即把b倒过来)

就转换成了求一个非下降的序列(因为b是非升序的,倒过来后b就变为非降序的了,与a连接,ai<=bi,所以连在一起就是一个非降序的了)

用一个二维数组d[i][j]

i表示长度,j表示在i长度下的最后一个数

整体表示为长度为i,最后一个数为j的情况下有多少种序列

方程:d[i][j]=d[i-1][j]+d[i][j-1]

代码:

#include <bits/stdc++.h>
using namespace std;
int d[25][1010];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {d[1][i]=1;}
    for(int i=2;i<=2*m;i++)
    {
        for(int j=1;j<=n;j++)
        {d[i][j]=(d[i-1][j]%1000000007+d[i][j-1]%1000000007)%1000000007;}
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=(ans%1000000007+d[2*m][i]%1000000007)%1000000007;
    }
    cout<<ans<<endl;
    return 0;
}

123

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注