Codeforces 351(#204 Div1) E. Jeff and Permutation

問題

数列a[i]が与えられる。各a[i]の符号を好きに変えてよい。
このとき、a[i]の転置(i < jかつa[i] > a[j])の個数の最小値はいくつか求めよ。

制約条件

n≦3000

方針

a[i]の絶対値が全て異なるとする。
すると、絶対値がx < yなるx, yがあったとき、xの符号がどうであってもyの符号で転置になるかそうでないかが決まる。
なので、絶対値の小さい順に符号を貪欲に決めていけばよい。


a[i]に絶対値が同じものが複数あるときは、そのa[i]の値のものを一度に処理する。
その値でdpをしてやる。
dp[i][j] := iまでで+をj個使ったときの転置の増加の最小値
i番目を+にすると、それ以降のa[i]より絶対値が小さいものの個数転置が増え、
i番目を-にすると、それまでのa[i]より絶対値が小さいものおよびa[i]で+にした個数転置が増える。


a[i]より絶対値が小さいものの個数はbinary indexed treeを使えば速く数えられる。

ソースコード

const int MX = 2010;
int n, a[MX];
vi pos[MX];

int ans;
int bit[MX];
int sum(int i){
	int res = 0;
	for(i++ ; i; i -= i & -i) res += bit[i];
	return res;
}
void add(int i, int x){
	for(i++ ; i < MX; i += i & -i) bit[i] += x;
}

void solve(int idx){
	const vi &v = pos[idx];
	int m = v.size();
	int cur = 0, next = 1;
	vector<vi> dp(m + 1, vi(m + 1, inf));
	
	dp[0][0] = 0;
	int tot = sum(n);
	
	rep(i, m){
		int l = sum(v[i]), r = tot - l;
		
		rep(j, i + 1) if(dp[i][j] < inf){
			dp[i + 1][j + 1] = min(dp[i + 1][j + 1], dp[i][j] + r); //+
			dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + l + j); //-
		}
	}
	ans += *min_element(all(dp[m]));
	rep(i, m) add(v[i], 1);
}

int main(){
	cin >> n;
	vi v;
	rep(i, n){
		cin >> a[i]; a[i] = abs(a[i]);
		v.pb(a[i]);
	}
	v.pb(0);
	sort(all(v));
	v.erase(unique(all(v)), v.end());
	
	rep(i, n){
		a[i] = lower_bound(all(v), a[i]) - v.begin();
		pos[a[i]].pb(i);
	}
	rep(i, pos[0].size()) add(pos[0][i], 1);
	for(int i = 1; i < MX && pos[i].size(); i++) solve(i);
	cout << ans << endl;
	return 0;
}