【CodeVS 2845】排序的代价（sort）/ 题解

Origin

Statement

There is a list of numbers to sort (ascending). Sorting can only be achieved through exchanges. Each exchange, you can choose any two of this column, exchange their positions, and the cost of the exchange is the sum of the two numbers. The total cost of sorting is the sum of all exchange costs in the sorting process. The first requirement is to calculate that for any given number of columns, it must be ranked as the minimum cost required for ascending order.

Idea

样例是 8 1 2 4
我们要让它 1 2 4 8
发现这种移动形成了一个环，我们把这种环称作“轮换”。
在一个序列中可能存在多个互相独立的轮换，我们可以对每个轮换求最优解，最后相加得到答案。
可以证明，对于一个n个数的轮换，最优解是进行n-1次操作。显然是用其中最小的数不断进行交换。也有可能存在的情况是，我们将整个序列里的最小数与轮换中的最小数交换，用这个数不断进行交换。所以只要取min就可以了。

Code

#include 
using namespace std;
int f[207][607],Tlim,id;
void dfs(int u){
    int len,x;cin>>len>>x;
    len*=2;if (x){
        for (int i=len;i<=Tlim;i++)
            f[u][i]=min(x,(i-len)/5);
        return;
    }
    int l=++id,r=++id,dfs(l),dfs(r);
    for (int i=len;i<=Tlim;i++)
        for (int j=0;j<=i-len;j++)
            f[u][i]=max(f[u][i],f[l][j]+f[r][i-len-j]);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>Tlim;
    dfs(0);
    cout<