傳送門
文章目錄
題意：
n≤5000n\le5000n≤5000
思路：
從dpdpdp題集中看到的，一看n≤5000n\le5000n≤5000，這不就亂搞就行了，哪有什么dpdpdp🦆。
看到冒泡排序，一般跟逆序對脫不了關系了，所以定義change[i][j]change[i][j]change[i][j]表示將iii放到jjj位置的時候逆序對變化數量，這個可以O(n2)O(n^2)O(n2)預處理出來，讓后n2n^2n2枚舉i,ji,ji,j計算答案就行了。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
#define lowbit(x) ((x)&(-x))
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=5010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
;
int a
[N
];
LL tr
[N
];
int change
[N
][N
];int main()
{
cin
>>n
;for(int i
=1;i
<=n
;i
++) {scanf("%d",&a
[i
]);int cnt1
,cnt2
; cnt1
=cnt2
=0;for(int j
=i
-1;j
>=1;j
--) {change
[i
][j
]=cnt1
-cnt2
;if(a
[j
]<a
[i
]) cnt1
++;else cnt2
++;}}for(int i
=n
;i
>=1;i
--) {int cnt1
,cnt2
; cnt1
=cnt2
=0;for(int j
=i
+1;j
<=n
;j
++) {change
[i
][j
]=cnt2
-cnt1
;if(a
[j
]<a
[i
]) cnt1
++;else cnt2
++;}}int sum
=0;for(int i
=1;i
<=n
;i
++) {for(int j
=i
+1;j
<=n
;j
++)sum
+=a
[i
]>a
[j
];}int ans
=INF
,cnt
=0;for(int i
=1;i
<=n
;i
++) {for(int j
=i
+1;j
<=n
;j
++) {int add
=0;if(a
[i
]<a
[j
]) add
++;else add
--;add
+=change
[i
][j
]+change
[j
][i
];if(add
<ans
) ans
=add
,cnt
=1;else if(add
==ans
) cnt
++; }}cout
<<sum
+ans
<<' '<<cnt
<<endl
;return 0;
}
總結
以上是生活随笔為你收集整理的Codeforces Round #212 (Div. 2) C. Insertion Sort 思维的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
