记录编号	186104	评测结果	AAAAAAAAAAA
题目名称	[BOI 2007]名次排序	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.081 s
提交时间	2015-09-11 16:05:37	内存使用	6.15 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<deque>
using namespace std;
const int INF=0x7fffffff/2;
int N,S[1010]={0},pos[1010]={0},C[1010]={0};
int father[1010][1010]={0};
int f[1010][1010]={0};
bool use[1010]={0};
deque<pair<int,int> > Q;
deque<int> P;
deque<int>::iterator it;
int ans;
class poi
{
public:
	int p,id;
};
bool cmp(poi a,poi b)
{
	return a.p>b.p;
}
void out()
{
	for(int i=1;i<=N+1;i++)
		P.push_back(S[i]);
	for(int i=N;i>=1;i--)
	{
		if(use[i]) continue;
		int pos1=0,pos2=0;
		it=find(P.begin(),P.end(),i);
		pos1=distance(P.begin(),it)+1;
		P.erase(it);
		it=find(P.begin(),P.end(),i+1);
		pos2=distance(P.begin(),it)+1;
		P.insert(it,i);
		Q.push_back(make_pair(pos1,pos2));
	}
	printf("%d\n",Q.size());
	for(int i=0;i<Q.size();i++)
		printf("%d %d\n",Q[i].first,Q[i].second);
}
void DP()
{
	for(int i=1;i<=N+1;i++) f[N+1][i]=INF;
	f[N+1][N+1]=0;
	for(int i=N;i>=1;i--)
	{
		int v=1;
		for(int j=1;j<pos[i];j++)
			if(S[j]<i) v++;//在i位置之前，比i小的数的个数
		int v2=1;
		for(int j=1;j<=N+1;j++)//把i移到哪个位置
		{
			if(S[j]<i) v2++;
			f[i][j]=f[i+1][j]+v+v2;
			father[i][j]=j;
		}
		int add=0;
		for(int j=pos[i]+1;j<=N+1;j++)
		{
			int cost=f[i+1][j]+add;
			if(f[i][pos[i]]>cost)
			{
				f[i][pos[i]]=cost;
				father[i][pos[i]]=j;
			}
			if(S[j]<i) add+=(i-S[j]);
		}
	}
	int ma=INF,s=-1;
	/*for(int i=1;i<=N+1;i++)
		for(int j=1;j<=N+1;j++)
			cout<<i<<" "<<j<<" "<<f[i][j]<<" "<<father[i][j]<<endl;*/
	for(int i=1;i<=N+1;i++)
	{
		if(f[1][i]<ma)
		{
			ma=f[1][i];
			s=i;
		}
	}
	for(int i=1;i<=N+1;i++)//那些人在原来的位置上(没有主动移动）
	{
		if(s==pos[i]) use[i]=1;
		s=father[i][s];
	}
	use[N+1]=1;
	out();
}
int main()
{
	freopen("sorting.in","r",stdin);
	freopen("sorting.out","w",stdout);
	scanf("%d",&N);
	poi A[1010];
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&A[i].p);
		A[i].id=i;
	}
	sort(A+1,A+1+N,cmp);
	for(int i=1;i<=N;i++)
	{
		pos[i]=A[i].id;
		S[pos[i]]=i;
	}
	S[N+1]=N+1;
	pos[N+1]=N;
	//for(int i=1;i<=N;i++) cout<<S[i]<<" ";
	DP();
	return 0;
}