Bzoj 5196: [Usaco2018 Feb]Taming the Herd (dp)

Solution f[i][j]f[i][j] indicates beforeiiDay experienced an escapejj次, andi+1i+1 Day fledf[i][j]=min(f[k][j1]+count(k+1,i))f[i][j]=min(f[k][j1]+count(k+1,i)) 其中 count(x,y)count(x,y) indicatesaxayaxay andDifference number of 1,2yx+11,2yx+1 So we can getn4n4Violence But we can preprocess thiscountcountUsecnt[i][j]cnt[i][j] indicatesaiajaiaj and0,1ji0,1ji Then you can get onen3n3dp

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1010
#define inf 0x3f3f3f3f
int n,a[N],cnt[N][N],f[N][N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    //i-j and 0..j-i
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            for(int k=0;k<=j-i;k++){
                cnt[i][j]+=(a[i+k]!=k);
            } 
        }
    }
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            for(int k=0;k<i;k++){
                if(f[k][j-1]==inf) continue;
                f[i][j]=min(f[i][j],f[k][j-1]+cnt[k+1][i]);
            }
        }
    }
    for(int i=1;i<=n;i++) printf("%d\n",f[n][i]);
    return 0;
}