Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

DP过了 哈哈,说下思路

Posted by lijingwei at 2010-08-20 11:31:33 on Problem 2323
先是一张表
   0  1  2  3  4  5  6  7  8  9  10
1  1    
2  1  1    
3  1  2  2  1
4  1  3  5  6  5  3  1  
5  1  4  9  15 20 22 20 15 9  4  1
6  1  5  14 29 49 71 90 101 101 90 
7  1  6  20 49 98 169 259 359 455。。。
a[i][j] 先初始化a[i][0],a[i][1];
然后循环   j大于i*(i-1)/4时a[i][j]=a[i][i*(i-1)/2-j];
j<i*(i-1)/4时
分情况
1.j<i时   a[i][j]=a[i-1][0]+a[i-1][1]+...a[i-1][j],
比如说i=4,j=3时  i-1是3;分别为 
123  逆序0    这时再第一位加一个4 成为4123  逆序3    
132 213  逆序1        第二位加4 1423  2413 逆序3
231 312 逆序2   。。。
321 逆序3   。。。
可以得出a[i][j]=a[i][j-1]+a[i-1][j];
2.j>i时    
a[i][j]=a[i][j-1]+a[i-1][j]-a[i-1][j-i];
因为a[i-1][j-i]怎么改也成不了a[i][j],比如a[6][6]=a[6][5]+a[5][6]-a[5][0];我也是枚举后发现的,12345在哪里加6逆序对不会成为6.


Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator