Farmer John 正在将他的 N 头奶⽜ ( 1≤N≤105 ) 排成⼀排，⽅便地编号为 1…N ，以便拍照。 最初，奶⽜从左到右按照 a1,a2,...,aN 的顺序排列 。Farmer John 的⽬标是按照 b1,...,bN 从左 到右的顺序排列奶⽜。为此，他可以对排序进⾏⼀系列修改。每个修改都包括选择⼀头奶⽜ 并将其向左移动⼀些位置。 请计算农⺠约翰按所需顺序排列奶⽜所需的最少修改次数

题目翻译

农夫 John 正在将他的 $N$ 头奶牛 $(1\leq N\leq 10^5)$ 排成一排，方便地编号为 $1…N$，以便拍照。最初，奶牛从左到右按照 $a_1,a_2,...,a_N$ 的顺序排列。农夫 John 的目标是按照 $b_1,...,b_N$ 从左到右的顺序排列奶牛。为此，他可以对排序进行一系列修改。每个修改都包括选择一头奶牛并将其向左移动一些位置。请计算农夫 John 按所需顺序排列奶牛所需的最少修改次数。

题解

这道题其实是一道经典的贪心问题——交换相邻逆序对。

首先，我们可以发现，对于第 $i$ 头奶牛，它需要向左移动的距离 $d_i$ 为 $b_i$ 在 $a$ 数组中的下标减去 $i$。也就是说，对于每头奶牛，我们都可以知道它需要向左移动的距离。

但是，我们并不需要真的进行移动，只需要记录每头奶牛需要向左移动的距离 $d_i$，并计算出它们的交换次数即可。

因为我们只能交换相邻两个位置上的奶牛，所以我们可以从左到右遍历 $b$ 数组，对于每个 $b_i$，我们找到它在 $a$ 数组中的位置 $j$，并把 $a_j$ 与 $a_{j-1}$ 交换，直到 $a_j$ 到达 $i$ 的位置。

为什么这个方法是正确的呢？因为我们每次都是交换相邻逆序对，所以每次交换后，我们就让一个相邻逆序对消失了。因此，我们最多只需要进行 $N$ 次交换。

代码

相关问题

有 N（1≤N≤105）头奶牛，每头奶牛的品种是更赛牛（Guernsey）或荷斯坦牛（Holstein）之一。她们沿水平方向排成一行，奶牛们占据的位置编号为 1…N。 由于奶牛们都饿了，FJ 决定在 1…N 中的某些位置上种植草地。更赛牛和荷斯坦牛喜欢不同类型的草，所以如果 Farmer John 决定在某个位置种草，他必须选择种植更赛牛喜欢的草或荷斯坦牛喜欢的草——他不能在同一个位置同时种两种草。种植的每一片草地都可以喂饱数量不限的相应品种的奶牛。 每头奶牛愿意移动至多 K （0≤K≤N−1）个位置以前往一个草地。求出喂饱所有奶牛所需种植的最小草地数量。此外，输出一种使用最小草地数量喂饱所有奶牛的种植方案。任何满足上述条件的方案均视为正确。

N 头奶牛沿水平方向排成一行，每头奶牛的品种是更赛牛或荷斯坦牛之一。FJ 要在 1…N 之间的某些位置上种植草地，但是每头奶牛只喜欢特定品种的草。每头奶牛愿意移动至多 K 个位置到达一个草地。求出喂饱所有奶牛所需的最小草地数量，并输出一种使用最少草地数量的喂饱所有奶牛的方案。

题目描述 Farmer John有n（1≤n≤2000）个美味的食物，他想卖掉它们来赚钱给奶牛。这些食物放在一些箱子里，它们有些有趣的特性： （1）这些食物被编号为1-n，每一天Farmer John可以从这排箱子的头部或者尾部取出食物去卖； （2）这些食物放得越久，年龄越大，价值越大，食物i有一个初始的价值v（i）； （3）放了a天后，年龄为a，食物最终的价值为v（i）×a。 给定每一个食物的初始价值v（i），请求出FJ卖掉它们后可以获得的最大价值，第一天出售的食物年龄为1，此后每增加一天食物的年龄就增加1。 输入格式 第一行，一个整数n； 第2×n+1行，每行为食物i的初始价值v（i）。 输出格式 一行，为FJ最终可以获得的最大价值。给出完整的c++代码

以下是C++代码实现：

#include<iostream>
#include<cstring>

using namespace std;

const int N = 2010;

int n;
int v[N];
int dp[N][N];

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> v[i];

    memset(dp, 0xc0, sizeof dp);  // 将dp数组初始化为负无穷

    for(int i = 1; i <= n; i++) dp[i][i] = n * v[i]; // 初始化dp数组

    for(int len = 2; len <= n; len++)  // 枚举区间长度
        for(int l = 1; l + len - 1 <= n; l++)  // 枚举区间左端点
        {
            int r = l + len - 1;  // 区间右端点
            dp[l][r] = max(dp[l + 1][r] + v[l] * (n - len + 1), dp[l][r - 1] + v[r] * (n - len + 1));
        }

    cout << dp[1][n] << endl;

    return 0;
}

算法思路：

这是一道区间DP的题目，我们可以用dp[l][r]表示区间[l, r]内能够获得的最大价值。因为每天卖出的食物年龄都会增加1，因此我们可以用n - len + 1表示第一天卖出的食物年龄。

状态转移方程为：dp[l][r] = max(dp[l + 1][r] + v[l] * (n - len + 1), dp[l][r - 1] + v[r] * (n - len + 1))，表示在区间[l, r - 1]中卖掉一件食物或在区间[l + 1, r]中卖掉一件食物，取最大值即可。

时间复杂度为O(n ^ 2)。