题解 P4267 【[USACO18FEB]Taming the Herd】

· · 题解

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

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

那么接下来我们就发现$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]);
}