终结小鸭|动态规划|题解

链接：https://ac.nowcoder.com/acm/contest/9045/E

E - 终结小鸭

题目描述

假设桂电有2×N只小白鸭，在同学们的精心照顾下长得十分肥美，是时候送上餐桌了。现在，学校打算将鸭子关进一个有2×N个格子的笼子中，要求同一行中右边格子里的鸭子比左边的重，同一列中下边格子里的鸭子比上边的重。已知鸭子的重量都不相同，请问一共有多少种方案？ （N为自然数）

输入样例

一个自然数N
对于40%的数据，N<200

对于70%的数据，N <1000

对于100%的数据, N <2000

输入样例

2

输出样例

2

    然后思路是这样的，由于是动态规划的问题，所以都要去画二维数组图😄(大家最好养成好习惯)，这道题还算一般般，因为这是一个二维的动态规划题，在动态规划里边只能算是中等水平的题目，详解就在下图

现在放代码😁😁😁😁(c++)

#include<bits/stdc++.h>
using namespace std;
int main(){
    int str[107][107];
    int t;
    cin>>t;
       for(int i=1;i<=t+1;i++){
     str[i][1]=0;
     str[1][i]=1;}
     for(int i=2;i<=t+1;i++){
         for(int j=i;j<=t+1;j++){

             if(i == j)
            str[i][j]=str[i-1][j]%1000;
            else
            str[i][j]=(str[i-1][j]+str[i][j-1])%1000;

         }
     }

    cout<<str[t+1][t+1]<<endl
    return 0;
}
、

这里要注意因为当时的疏忽，在比赛结束后我们审题的时候意外发现在当t的数量超过20的时候，方法数会暴增以至于根本无法得到有效的数字😂😂😂😂，所以这也是但是的遗憾吧，没和大家说清楚这个事，所以所有的数字都要%1000才行。