1996: [Hnoi2010]chorus 合唱队

Time Limit: 4 Sec  Memory Limit: 64 MB

Submit: 1057  Solved: 681

[][][]

Description

Input

Output

Sample Input

4

1701 1702 1703 1704

Sample Output

8

HINT

 

Source

 

 

题解：萌萌哒DP题，其实和我一开始想的暴力方法很接近，基本上就是记忆化暴力，然后转变为循环形式（HansBug：无后效性这玩意就是爽^_^），然后就只管AC啦

（PS：不过话说第一遍的记忆化暴力WA掉了是What Ghost？？？）

1 /************************************************************** 2     Problem: 1996 3     User: HansBug 4     Language: Pascal 5     Result: Accepted 6     Time:108 ms 7     Memory:8172 kb 8 ****************************************************************/ 9  10 const p=19650827;11 var12    i,j,k,l,m,n:longint;13    c:array[0..10000] of longint;14    a:array[0..1005,0..1005,1..2] of longint;15 begin16      readln(n);17      for i:=1 to n do18          begin19               read(c[i]);20               a[i,i,0]:=1;21          end;22      readln;23      for i:=n-1 downto 1 do24          for j:=i+1 to n do25              begin26                   a[i,j,0]:=0;a[i,j,1]:=0;27                   if c[i]
      
       c[i] then inc(a[i,j,1],a[i,j-1,0]);30                   if c[j]>c[j-1] then inc(a[i,j,1],a[i,j-1,1]);31                   a[i,j,0]:=a[i,j,0] mod p;32                   a[i,j,1]:=a[i,j,1] mod p;33              end;34      writeln((a[1,n,1]+a[1,n,0]) mod p);35      readln;36 end.