首页 > 搜索 > DFS搜索 > hdu 1320 Inversion-DFS-[解题报告]
2013
12-09

hdu 1320 Inversion-DFS-[解题报告]

Inversion

问题描述 :

Let { A1,A2,…,An } be a permutation of the set{ 1,2,…, n}. If i < j and Ai > Aj then the pair (Ai,Aj) is called an "inversion" of the permutation. For example, the permutation {3, 1, 4, 2} has three inversions: (3,1), (3,2) and (4,2).
The inversion table B1,B2,…,Bn of the permutation { A1,A2,…,An } is obtained by letting Bj be the number of elements to the left of j that are greater than j. (In other words, Bj is the number of inversions whose second component is j.) For example, the permutation:
{ 5,9,1,8,2,6,4,7,3 }
has the inversion table
2 3 6 4 0 2 2 1 0
since there are 2 numbers, 5 and 9, to the left of 1; 3 numbers, 5, 9 and 8, to the left of 2; etc.
Perhaps the most important fact about inversions is Marshall Hall’s observation that an inversion table uniquely determines the corresponding permutation. So your task is to convert a permutation to its inversion table, or vise versa, to convert from an inversion table to the corresponding permutation.

输入:

The input consists of several test cases. Each test case contains two lines.
The first line contains a single integer N ( 1 <= N <= 50) which indicates the number of elements in the permutation/invertion table.
The second line begins with a single charactor either ‘P’, meaning that the next N integers form a permutation, or ‘I’, meaning that the next N integers form an inversion table.

输出:

For each case of the input output a line of intergers, seperated by a single space (no space at the end of the line). If the input is a permutation, your output will be the corresponding inversion table; if the input is an inversion table, your output will be the corresponding permutation.

样例输入:

9
P 5 9 1 8 2 6 4 7 3
9
I 2 3 6 4 0 2 2 1 0
0

样例输出:

2 3 6 4 0 2 2 1 0
5 9 1 8 2 6 4 7 3

解题转自:http://aoxuemugualu.blog.163.com/blog/static/191501202201310883637874/


  1. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks