Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
DP过了 哈哈,说下思路先是一张表 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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator