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

z55250825

一只蒟蒻

 
 
 

日志

 
 

【Bzoj1996】【Hnoi2010】【合唱队chorus】  

2014-04-23 10:10:44|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
   题目大意:给某个双端队列插入元素,每一次用当前要插入元素和上一个元素相比【第一个直接插到队列里去..】,如果大于它上一个元素的话就插到最右边,否则插到最左边。然后给出最后双端队列的元素的排列顺序,询问有多少种初始插入顺序能得到这个插入后的顺序?

    0.0咱们首先的想法自然就是搜索【神犇:首先的想法不应该是...【捂嘴】】...咱们倒着搜,每次从左边或者右边选出一个元素,然后判断它和上一次选出的元素的合法性【合法性就比如其中一个是如果上一个元素在右边的话,那么它就必须要大于那个元素】,然后再继续选,直到选完了ans++,但是这显然会TLE...
    注意到,假设咱们两次搜索到了同一个局面,那么第二次搜索出的那个答案的个数显然和第一个是相同的,即咱们可以用当前的局面来表示一个状态,即用【l,r】表示左右端点就可以来表示一个状态了,也就是说状态总数只有O(n^2)级别的...这里就是DP了额0.0,所以大概就这些了= =....【话说为什么咱不直接说是DP额...】

    设 f[i][j] 表示左端点为i,右端点为j的原子序列被摆放出来的方案数,考虑决策,咱们发现决策跟取左边还是右边有关额...,所以咱们加一维f[i][j][k],k=0表示取左边的,k=1表示取右边的。然后转移,

    考虑取左边的,即f[i][j][0] 局面变成 f[i+1][j],因为a[i]在左边,所以小于上一个元素。所以 当 a[i+1]>a[i]的时候可以用 f[i+1][j][0]转移,a[j]>a[i]的时候可以用 f[i+1][j][1]转移。

     同理可以整理出右边的来。

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

program bzoj1996;
const modd=19650827;
var f:array[0..1010,0..1010,0..1]of int64;
    a:array[0..1010]of longint;
    n:longint;
    ans:int64;

procedure init;
var i,j,k:longint;
begin
  read(n);
  for i:=1 to n do read(a[i]);
  fillchar(f,sizeof(f),0);
  for i:=1 to n do
   begin
    f[i][i][0]:=1;
    f[i][i][1]:=1;
   end;
  for j:=2 to n do
   for i:=1 to n-j+1 do
    begin
      k:=i+j-1;
      if a[i]<a[i+1] then
       begin
        f[i][k][0]:=f[i][k][0]+f[i+1][k][0];
        if f[i][k][0]>=modd then dec(f[i][k][0],modd);
       end;
      if (i+1<>k)and(a[i]<a[k]) then
       begin
        f[i][k][0]:=f[i][k][0]+f[i+1][k][1];
        if f[i][k][0]>=modd then dec(f[i][k][0],modd);
       end;
      if a[k]>a[k-1] then
       begin
        f[i][k][1]:=f[i][k][1]+f[i][k-1][1];
        if f[i][k][1]>=modd then dec(f[i][k][1],modd);
       end;
      if (i+1<>k)and(a[k]>a[i]) then
       begin
        f[i][k][1]:=f[i][k][1]+f[i][k-1][0];
        if f[i][k][1]>=modd then dec(f[i][k][1],modd);
       end;
    end;
  ans:=(f[1][n][0]+f[1][n][1])mod modd;
  write(ans);
end;

begin
  init;
end.


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

历史上的今天

评论

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

页脚

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