題意/Description：

? ? These days, Sempr is crazed on one problem named Crazy Thair. Given?N?(1 ≤?N?≤ 50000) numbers, which? are no more than 10⁹, Crazy Thair is a group of 5 numbers {i,?j,?k,?l,?m} satisfying:

? ? 1. 1 ≤?i?<?j?<?k?<?l?<?m?≤?N

?

? ? 2.?A_i?<?A_j?<?A_k?<?A_l?<?A_m

? For example, in the sequence {2, 1, 3, 4, 5, 7, 6},there are four Crazy Thair groups: {1, 3, 4, 5, 6}, {2, 3, 4, 5, 6}, {1, 3, 4, 5, 7} and {2, 3, 4, 5, 7}.

Could you help Sempr to count how many Crazy Thairs in the sequence?

?

讀入/Input：

? Input contains several test cases. Each test case begins with a line containing a number?N, followed by a line containing?N?numbers.

?

輸出/Output：

? Output the amount of Crazy Thairs in each sequence.

?

題解/solution：

? 網上的解題報告有兩個解法：

? ? 1：Dp+線段樹+離散化+高精度

? ? 2：樹狀數組+Dp+離散化+高精度

? 靠，好復雜，又沒有P語言，C語言不會翻，I give up it。然后LZH經過了N天N夜，在 big head 的嘰嘰咕咕下，在 pig 的亂搞下，AC啦。于是我狠狠的敲了一波標。

? 講一下DP：

? ? F[I,j]表示用a[i]結尾的長度為j的序列數目。

? ? F[I,j]= sum(F[k,j-1])?(1<=k<I且a[i]>a[k])

? 因為讀入的數有10^9大，而數列長度只有50000，想到離散化。可離散后，位置發生改變，排個序，在二分來查找。

要找它前方的所有比它小的樹的t-1之和，想到了單點更新區間查詢，線段樹和數狀數組都可以維護。由于長度為5，用5個樹。完成這些，會發現結果會爆int64，于是加個高精度。看完后，你肯定。 ? 代碼/Code：
typearr=recordx,y:longint;end;vardp:array [0..50001,1..5] of int64;m,len,n,k:longint;f:array [0..50001] of longint;tree:array [0..50001] of arr;sum:array [0..101] of longint;procedure qsort(l,r:longint); vari,j,key,key1:longint;temp:arr; beginif l>=r then exit;i:=l; j:=r;key:=tree[(l+r) shr 1].x;key1:=tree[(l+r) shr 1].y;repeatwhile (tree[i].x<key) or (tree[i].x=key) and (tree[i].y<key1) do inc(i);while (tree[j].x>key) or (tree[j].x=key) and (tree[j].y>key1) do dec(j);if i<=j thenbegintemp:=tree[i]; tree[i]:=tree[j]; tree[j]:=temp;inc(i);dec(j);end;until i>j;qsort(l,j);qsort(i,r); end;function bit(n:longint):longint; beginexit(n and -n); end;procedure jf(n:qword); vari:longint;a,b:array [0..100] of longint; beginfillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);i:=-1;while n>0 dobegininc(i);a[i]:=n mod 10;n:=n div 10;end;i:=-1;while i<100 dobegininc(i);b[i]:=a[i]+sum[i]+b[i];if b[i]>=10 thenbegininc(b[i+1]);b[i]:=b[i] mod 10;end;end;for i:=0 to 99 dosum[i]:=b[i]; end;function count(n,j:longint):int64; varans:int64; beginans:=0;while n>0 dobeginans:=ans+dp[n,j];n:=n-bit(n);end;exit(ans); end;procedure update(n,j:longint;k:int64); beginwhile n<=m dobegindp[n,j]:=dp[n,j]+k;n:=n+bit(n);end; end;procedure dpp(n:longint); vartem:int64;i,j:longint; beginfillchar(dp,sizeof(dp),0);fillchar(sum,sizeof(sum),0);len:=1;for i:=1 to n dobegintem:=count(f[i]-1,4);jf(tem);for j:=5 downto 2 dobegintem:=count(f[i]-1,j-1);update(f[i],j,tem);end;update(f[i],1,1);end;len:=100;while(sum[len]=0) and (len>0) do dec(len);for i:=len downto 0 dowrite(sum[i]);writeln; end;procedure main; vari:longint; beginwhile not eof dobeginreadln(n);m:=n;for i:=1 to n-1 dobeginread(tree[i].x);tree[i].y:=i;end;readln(tree[n].x);tree[n].y:=n;qsort(1,n);f[tree[1].y]:=1; k:=0;for i:=1 to n dobeginif tree[i].x=tree[i-1].x then f[tree[i].y]:=f[tree[i-1].y] elsebeginf[tree[i].y]:=k+1;inc(k);end;end;dpp(n);end; end;beginmain; end.

?

轉載于:https://www.cnblogs.com/zyx-crying/p/9319691.html

總結

以上是生活随笔為你收集整理的poj 3378 Crazy Thairs的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。