注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj2431】【HAOI2009】【逆序对数列】  

2014-05-04 16:11:03|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   题目大意:求1~n的排列中逆序对为K的有多少个。
   n<=1000,k<=1000。

   做水题涨信心,涨信心做水题。TvT
   很容易想到dp 0.0,这一次的状态貌似不是特别好引出...所以还是直接说了吧= =,咱们设 f[i][j]表示前i个数逆序对为j的方案数,然后咱们考虑插入一个数i+1,实际上无论它插在哪里,它之前的数都比它小,不会产生逆序对,所以产生逆序对的地方是在后面,咱们枚举插在哪里的话,就可以得到dp方程 f[i][j]=∑f[i-1][j-k](0<=k<=i-1且j-k>=0)状态数是O(nk)的,但是转移却可以达到O(n)一次,所以需要化简,实际上容易观察到这可以通过弄前缀和得到= =即咱们记录一个s[],当转移到f[i][]的时候,s[]为f[i-1]的前缀和,然后咱们只需要计算出区间然后用前缀和加加减减即可。

=====================

const modd=10000;
var f:array[0..1010,0..1010]of longint;
    s:array[-1..1010]of longint;
    n,k:longint;

function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;

function max(a,b:longint):longint;
begin
  if a>b then exit(a) else exit(b);
end;

function cal(n:longint):longint;
begin
  exit(n*(n-1)shr 1);
end;

procedure init;
var i,j,l:longint;
begin
  read(n,k);
  f[0][0]:=1;
  fillchar(s,sizeof(s),0);
  fillchar(f,sizeof(f),0);
  for i:=0 to k do s[i]:=1;
  for i:=1 to n do
   begin
     for j:=0 to min(k,cal(i)) do
      begin
        l:=max(j-(i-1),0);
        f[i][j]:=(s[j]-s[l-1]+modd)mod modd;
      end;
     for j:=0 to k do
       s[j]:=(s[j-1]+f[i][j])mod modd;
   end;
  write(f[n][k]);
end;

begin
  init;
end.


  评论这张
 
阅读(61)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018