约定(模拟赛2 T3)

题目描述

小A在你的帮助下成功打开了山洞中的机关，虽然他并没有找到五维空间，但他在山洞中发现了无尽的宝藏，这个消息很快就传了出去。人们为了争夺洞中的宝藏相互陷害，甚至引发了战争，世界都快要毁灭了。小A非常地难过，小A希望能成为天下第一的高手来拯救世界，于是他决定来到著名的X城，他遇到了许多新事物和前所未有的挑战，背井离乡的日子难免有忧伤和孤单，不过幸运的是小A结识了志同道合的小雪，因为彼此的存在他们不再孤单。在星空下，小A和小雪做了一个约定：一起寻找拯救这崩坏世界的方法。这时出现了一位神秘人告诉小A他能够帮助实现小A的梦想，但现在有一个问题。
神秘人有一套魔法牌，一共有 𝑛n 张，分别标着 11 到 𝑛n 的编号。我们现在可以把这 𝑛n 张牌随意排列，每两个相邻的数之间都有着大小关系，这样每种排列都会有 𝑛−1n−1 个关系，我们把前一个数小于后一个数这种关系称为“有效关系”，而如果说一种排列恰好有 𝑘k 个“有效关系”，那么摆出这样的排列就能提供 11 点灵力值，同一种排列只会提供一次灵力值。现在神秘人需要知道通过尝试不同的排列最多能够获得多少灵力值，这将影响着他下一步该如何帮助小A。
由于这个问题的答案可能非常的大，小A根本算不明白，而神秘人只会魔法，于是小A希望你能帮他解决这个问题。答案对2012取模。

输入描述

第一行两个整数 𝑛,𝑘

输出描述

一个整数表示答案。

输入样例

3

1

输出样例

4

用dp紫腚~~~~~~~~~~~~~~能过(不过我直接chishi）

这道题本蒟蒻用dp轻松AC了

直接上AC代码

#include<bits/stdc++.h>
using namespace std;
int n,k;
int dp[1005][1005];
int main(){cin>>n>>k;for(int i=0;i<=n;i++) dp[i][0]=1;for(int i=1;i<=1000;i++){for(int j=1;j<=1000;j++){dp[i][j]=dp[i-1][j-1]*(i-j)+dp[i-1][j]*(j+1);dp[i][j]%=2012;}} cout<<dp[n][k];return 0;
}