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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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]);
}

 评论