洛谷p2401(不等数列)——蒟蒻题解


膜你赛T2——不等数列(洛谷p2401 ps:膜数不一样)

刚开始打了30分的打表(手推不出规律

因为T1看错题了导致两小时全栽在T1上(

中午开始思考推规律

虽然同机房的说是杨辉三角,但是这方面我做的题不多,没法直接看出来

ps:因为打表时忘了处理0的情况,下意识以为没有<的个数肯定是零,其实还有全大于号的情况啊喂

于是去看题解思路

其实原来也想了是不是通过上面两种临近的情况推过来,所以看完题解豁然开朗,下面写出思路

所以上面的都是废话

洛谷p2401(不等数列)——蒟蒻题解

首先我们举一个例子

1<2<31<2<3

1<2<3 和

1<3>21<3>2

1<3>2这是当

nn

n等于

33

3时的其中两种

当我们处理

n=4n=4

n=4 时,可以从上面的情况推下来

插入一个

44

4,此时

44

4为最大值
如果插入到两边:左边会增加一个大于号(无关),右边的话会增加一个小于号
如果插入中间:在

1<2<31<2<3

1<2<3的

1,21,2

1,2中间插入,会减少一个小于号并增加一个小于号和一个大于号

1<4>2<31<4>2<3

1<4>2<3,即为增加一个大于号,与小于号无关
插入中间的第二种:将大于号替换:在

1<3>21<3>2

1<3>2中的

3,23,2

3,2中间插入,会减少一个大于号并增加一个大于号,一个小于号

1<3<4>21<3<4>2

1<3<4>2,即为增加一个小于号
总结就是在 右面添加新数 或者在 中间替换大于号 才会改变当前小于号的数量;

得到了规律我们可以慢慢写出递推式(用

f[i][j]f[i][j]

f[i][j]表示

ii

i个数有

jj

j个小于号的排列数):

f[i+1][j]+=(j+1)f[i][j]f[i+1][j]+=(j+1)*f[i][j]

f[i+1][j]+=(j+1)∗f[i][j],

f[i+1][j+1]+=(ij)f[i][j]f[i+1][j+1]+=(i-j)*f[i][j]

f[i+1][j+1]+=(i−j)∗f[i][j]

只有这两个式子是因为每个排列都是由小于号少于它一个或者小于号与它相等的排列递推而来

第一个式子中

j+1j+1

j+1是因为包含了所有小于号的位置和最左边的位置

第二个式子中

iji-j

i−j为大于号的位置个数

根据这个式子可以很短很快的写出代码

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

泪目

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

洛谷p2401(不等数列)——蒟蒻题解

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 洛谷p2401(不等数列)——蒟蒻题解
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏