首页 > 其他 > 详细

bzoj 1996 DP

时间:2014-01-15 20:15:49      阅读:409      评论:0      收藏:0      [点我收藏+]

  我们可以发现,对于最后队列的一段区间[i,j],不论这一段区间如何插入,除了最后一个插入的对象外,剩下的对后续插入没有影响,这启发我们可以用DP来解决这一问题。

  w[i][j][0..1]代表区间[i,j],最后一个插入的元素是i(0)或者j(1)的方案数,那么就可以根据判断当前插入元素与上一元素的大小关系很容易的转移了。 

  

bubuko.com,布布扣
/**************************************************************
    Problem: 1996
    User: BLADEVIL
    Language: Pascal
    Result: Accepted
    Time:164 ms
    Memory:8216 kb
****************************************************************/
 
//By BLADEVIL
const
    d39                         =19650827;
     
var
    n                           :longint;
    i, j, l                     :longint;
    h                           :array[0..1010] of longint;
    w                           :array[0..1010,0..1010,0..1] of longint;
    ans                         :longint;
     
begin
    read(n);
    for i:=1 to n do read(h[i]);
     
    for i:=1 to n do
    begin
        w[i][i][0]:=1;
        w[i][i][1]:=1;
    end;
    for l:=1 to n-1 do
        for i:=1 to n-l do
        begin
            j:=i+l;
            if h[i+1]>h[i] then w[i][j][0]:=(w[i][j][0]+w[i+1][j][0]) mod d39;
            if i+1<>j then if h[j]>h[i] then w[i][j][0]:=(w[i][j][0]+w[i+1][j][1]) mod d39;
            if h[j]>h[i] then w[i][j][1]:=(w[i][j][1]+w[i][j-1][0]) mod d39;
            if i<>j-1 then if h[j]>h[j-1] then w[i][j][1]:=(w[i][j][1]+w[i][j-1][1]) mod d39;
        end;
    ans:=(w[1][n][0]+w[1][n][1]) mod d39;
    writeln(ans);
end.
 
bubuko.com,布布扣

bzoj 1996 DP

原文:http://www.cnblogs.com/BLADEVIL/p/3515349.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!