Gym

Problem C. The Problem Needs 3D Arrays

　　Time Limit: 6000MS Memory Limit: 262144KB 64bit IO Format: %I64d & %I64u

Description

A permutation is a sequence of integers p₁,p₂,...,p_n, consisting of n distinct positive integers and each of them does not exceed n. Assume that r(S) of sequence S denotes the number of inversions in sequence S (if i < j and S_i> S_j, then the pair of (i,j) is called an inversion of S), l(S) of sequence S denotes the length of sequence S. Given a permutation P of length n, it’s your task to find a subsequence S of P with maximum. A subsequence of P is a sequence (p_i₁,p_i₂,...,p_i_t) which satisfies that 0 < i₁< i₂< ... < i_t≤ n.

Input

The first line of the input gives the number of test cases, T. T test cases follow.

For each test case, the first line contains an integer n (1 ≤ n ≤ 100), the length of the permutation P. The second line contains n integers p₁,p₂,...,p_n, which represents the permutation P.

Output

For each test case, output one line containing “Case #x: y”, where x is the test case number (starting from 1) and y is the maximum.

Your answer will be considered correct if it is within an absolute error of 10−⁶of the correct answer.

Samples

Sample Input

Sample Output

3 4 2 5 1

Case #1: 1.250000000000

解题：最大密度子图转为最大权闭合图

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 12000;
 4 const int INF = 0x3f3f3f3f;
 5 int n,m,tot,S,T,x[maxn],y[maxn],A[102];
 6 struct arc {
 7     int to,next;
 8     double flow;
 9     arc(int x = 0,double y = 0,int z = -1) {
10         to = x;
11         flow = y;
12         next = z;
13     }
14 } e[maxn<<4];
15 int head[maxn],cur[maxn],d[maxn];
16 void add(int u,int v,double flow) {
17     e[tot] = arc(v,flow,head[u]);
18     head[u] = tot++;
19     e[tot] = arc(u,0,head[v]);
20     head[v] = tot++;
21 }
22 queue<int>q;
23 bool bfs() {
24     memset(d,-1,sizeof d);
25     while(!q.empty()) q.pop();
26     q.push(S);
27     d[S] = 1;
28     while(!q.empty()) {
29         int u = q.front();
30         q.pop();
31         for(int i = head[u]; ~i; i = e[i].next) {
32             if(e[i].flow > 0 && d[e[i].to] == -1) {
33                 d[e[i].to] = d[u] + 1;
34                 q.push(e[i].to);
35             }
36         }
37     }
38     return d[T] > -1;
39 }
40 double dfs(int u,double low) {
41     if(u == T) return low;
42     double tmp = 0,a;
43     for(int &i = cur[u]; ~i; i = e[i].next) {
44         if(e[i].flow > 0 && d[e[i].to] == d[u] + 1 &&(a=dfs(e[i].to,min(e[i].flow,low)))>0) {
45             e[i].flow -= a;
46             e[i^1].flow += a;
47             low -= a;
48             tmp += a;
49             if(low <= 0) break;
50         }
51     }
52     if(tmp <= 0) d[u] = -1;
53     return tmp;
54 }
55 bool dinic() {
56     double ans = m;
57     while(bfs()) {
58         memcpy(cur,head,sizeof head);
59         ans -= dfs(S,INF);
60     }
61     return ans <= 0;
62 }
63 void build(double delta) {
64     memset(head,-1,sizeof head);
65     for(int i = tot = 0; i < m; ++i) {
66         add(S,i + n + 1,1.0);
67         add(i + n + 1,x[i],INF);
68         add(i + n + 1,y[i],INF);
69     }
70     for(int i = 1; i <= n; ++i) add(i,T,delta);
71 }
72 int main() {
73     int cm = 1,cs;
74     scanf("%d",&cs);
75     while(cs--) {
76         scanf("%d",&n);
77         m = 0;
78         for(int i = 1; i <= n; ++i) {
79             scanf("%d",A+i);
80             for(int j = i-1; j > 0; --j)
81                 if(A[j] > A[i]) {
82                     x[m] = j;
83                     y[m++] = i;
84                 }
85         }
86         S = 0;
87         T = n + m + 1;
88         double low = 0,high = m,ans = 0;
89         if(m == 0) {printf("Case #%d: %.7f
",cm++,ans);continue;}
90         while(high - low > 1e-7){
91           double mid = (low + high)/2.0;
92           build(mid);
93           if(dinic()) ans = high = mid;
94           else low = mid;
95         }
96         printf("Case #%d: %.7f
",cm++,ans);
97     }
98     return 0;
99 }

View Code