[BOI2007]名次排序问题(sorting)

题目描述

已知参赛选手的得分，你的任务是按照得分从高到底给出选手的排名。遗憾的是，保存选手信息的数据结构只支持一种操作，即将一个选手从位置i移动到位置j，该移动不改变其他选手的相对位置，即如果i > j，位置j和位置i-1之间的选手的位置都比原来加1，相反如果 i < j，则位置i+1和位置j之间的选手的位置都比原来减一。上述移动的操作的代价定义为i+j，这里，位置编号从1开始。请你编程确定一个移动选手的步骤，将选手按照得分从高到低排序，并使整个移动过程的总代价最小。

输入

文件sorting.in第一行为一个整数n（2<=n<=1000），表示选手的人数；接下来的n行，每行一个非负整数Si( 0<=Si<=1000000)，表示一个选手的得分。你可以认为每人的得分是不同的。

输出

文件sorting.out的第一行为一个整数，表示移动的次数，接下来的每一行表示一个移动步骤，每个移动步骤用两个整数i, j表示，表示位置i的选手移动到位置j， i和j之间有一个空格隔开。

样例输入输出

soring.in
5
20
30
5
15
10
sorting.out
2
2 1
3 5

附原题pdf下载

原题pdf下载（English）

附原题数据下载

原题数据下载(已修改文件名，能被lemon等识别)

题解

本身我不想写，因为我是按照《对一类动态规划问题的研究》（湖南省长沙市第一中学 徐源盛）这篇论文上的思路写的代码，但是网上都没有代码，于是我就写了代码，本着分享的原则，将这篇文章截取下来吧。
同样这题属于当前决策对未来“行动”的费用影响只与当前决策有关的dp题目。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！