自动搬运

查看原文

来自洛谷，原作者为

	Dilute 为了那个梦我们扬帆启航，只为理应到来的那天跨过无数黑夜。

搬运于2025-08-24 21:58:21，当前版本为作者最后更新于2018-07-31 20:49:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

竟然没有人写题解2333那本蒟蒻就来$H_2O$一篇吧

首先，看完题面不难想到DP，之后再看数据范围考虑$O(N^3)$DP，之后瞎搞一通可以想到

$f[i][j]$表示在前$i$个里面经历$k$次出逃可以取到最少的修改数

那么接下来我们就发现$f[i][j]$可以影响的范围为$f[u][j+1]$($i < u ≤n$)，然后我们就可以写出如下的程序：

#include<bits/stdc++.h>

using namespace std;

int Num[110];
int Cnt[110][110];
int f[110][110]; // dp数组

int main(){
	memset(f, 127, sizeof(f)); // f数组初值极大
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", &Num[i]);
    /*
     * Cnt[i][j]表示如果第i天出逃那么到第j天如果改成输入的序列需要修改的次数
     * 这里我们把Cnt预处理以下
     */
	for(int i = 0; i <= n; i++){
		int Cou = 0;
		for(int j = i; j <= n; j++){
			if(Num[j] != j - i)
				Cou++;
			Cnt[i][j] = Cou;
		}
	}
    // dp
	f[0][0] = 0;
	for(int i = 0; i <= n; i++)
		for(int j = 1; j <= n; j++)
			for(int u = i+1; u <= n; u++) // 枚举f[i][j]可以更新的状态
				if(f[u][j] > f[i][j-1] + Cnt[i+1][u]) // 如果更优
					f[u][j] = f[i][j-1] + Cnt[i+1][u];
    // 不难看出答案就是f[n][1]……f[n][n]
	for(int i = 1; i <= n; i++)
		printf("%d\n", f[n][i]);
}