首页 > 其他分享 >不等数列 (Dp插入e)

不等数列 (Dp插入e)

时间:2022-10-25 12:01:34浏览次数:49  
标签:do begin end 数列 .. dfs 插入 longint Dp



【题目描述】

将1到n任意排列,然后在排列的每两个数之间根据他们的大小关系插入“>”和“<”。问在所有排列中,有多少个排列恰好有k个“<”。答案对2012取模。

 

【输入格式】

第一行2个整数n,k。

 

【输出格式】

一个整数表示答案。

 

【样例输入】

5 2

【样例输出】

66

【数据范围】

对于30%的数据:n <= 10

对于100%的数据:k < n <= 1000,





F[i,j]=f[i-1,j](j+1)+f[i-1][j-1](i-j)   i表示从1到i的数   j表示小于号个数

          插入最大数e后添了一个>

          或者一个<的数量


const
maxn=1000;
var
f:array[0..1000,0..1000] of longint;
n,i,j,k:longint;
begin
assign(input,'num.in');
assign(output,'num.out');
reset(input);
rewrite(output);
read(n,k);
if (k>n-1-k) then k:=n-1-k;
for i:=1 to n do
begin
f[i,0]:=1;
f[i,i-1]:=1;
end;
for i:=2 to n do
for j:=1 to k do
f[i,j]:=(f[i-1,j]*(j+1)+f[i-1,j-1]*(i-j)) mod 2012;
writeln(f[i,k]);
close(input);
close(output);
end.


另附 暴搜%30数据的版本

var
b:array[1..10] of boolean;
f:array[0..10] of longint;
n,k,i:longint;
procedure dfs(l,x,father:longint);
var
i:longint;
begin
if l=n then begin inc(f[x]); exit; end;
for i:=1 to n do
if not(b[i]) then
begin
b[i]:=true;
if father<i then dfs(l+1,x+1,i) else
dfs(l+1,x,i);
b[i]:=false;
end;

end;
begin
readln(n,k);
fillchar(b,sizeof(b),false);
fillchar(f,sizeof(f),0);
for i:=1 to n do
begin
b[i]:=true;
dfs(1,0,i);
b[i]:=false;
end;
for i:=0 to n-1 do write(f[i],' ');


end.




标签:do,begin,end,数列,..,dfs,插入,longint,Dp
From: https://blog.51cto.com/u_15724837/5794422

相关文章

  • ZOJ 2527(最长等差数列)
    随便给一串数列,求最长等差数列3方水过,回头附n^2logn算法(dp[i][j][k]=dp[i][k]+1)#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#include<cctype>#in......
  • LOJ #10005. 「一本通 1.1 练习 1」数列极差
    题目链接:​​传送门​​贪心题才是难的按照从小到大的顺序排,这样相乘会得到最大值,因为后面的最大值乘的更多最小值同理,就是从大到小处理就可以但是注意在操作的过程中不......
  • BZOJ 2111([ZJOI2010]Perm 排列计数-乘法逆元+完全二叉树模型+数列分数表示法)
    2111:[ZJOI2010]Perm排列计数TimeLimit: 10Sec  MemoryLimit: 259MBSubmit: 478  Solved: 283[​​Submit​​][​​Status​​][​​Discuss​​]......
  • fzu_noip 1036(磁盘碎片整理-Dp)
    磁盘碎片整理时限:1s内存:32M★问题描述:Jack最近在PS海报。海报所需各种素材不但让Jack头大,也让硬盘分区中的文件碎片越来越多,电脑的反应速度越来越慢。烦恼的Jack决定好好......
  • BZOJ 1084([SCOI2005]最大子矩阵-长矩阵Dp)
    1084:[SCOI2005]最大子矩阵TimeLimit: 10Sec  MemoryLimit: 162MBSubmit: 586  Solved: 275[​​Submit​​][​​Status​​][​​Discuss​​]De......
  • CF 286A(Lucky Permutation-数列找规律)
    A.LuckyPermutationtimelimitpertestmemorylimitpertestinputoutputp......
  • 如何用界面组件DevExpress WinForm创建一个支持High DPI的应用?
    DevExpressWinForm拥有180+组件和UI库,能为WindowsForms平台创建具有影响力的业务解决方案。DevExpressWinForms能完美构建流畅、美观且易于使用的应用程序,无论是Office......
  • Java多线程(3):ThreadPool(中)
    您好,我是湘王,这是我的博客园,欢迎您来,欢迎您再来~ 线程池是个神器,用得好会非常地方便。本来觉得线程池的构造器有些复杂,即使讲清楚了对今后的用处可能也不太大,因为有一些J......
  • ACSX 10 月专题训练:DP
    FreeMarkethttps://www.luogu.com.cn/problem/CF364B一个观察是第一个限制是无用的,原因在于你拿去的如果跟它有交你就只换没交的部分就行了。所以你手上一个总权值为X......
  • P2015 二叉苹果树 (树形DP)
    二叉苹果树题目描述有一棵苹果树,如果树枝有分叉,一定是分二叉(就是说没有只有一个儿子的结点)这棵树共有\(N\)个结点(叶子点或者树枝分叉点),编号为\(1\simN\),树根编号......