题解：SP16809 EST - Estimation

· · 题解

给出一种 O(n^2k) 的简单做法。

考虑一个简单的 dp，状态设计是 dp_{i,j,k} 表示考虑到第 i 个数，现在是第 j 段，现在的值是 a_k 的时候的答案。

dp_{i,j,k}=\min\{\min_{t=1}^{n}\{dp_{i-1,j-1,t}\},dp_{i-1,j,k}\}+|a_i-a_k|

解释一下，就是分别讨论从 i 新开一段或继承前面一段的答案。

我们发现 \min_{t=1}^{n}\{dp_{i-1,j-1,t}\} 可以预处理出来，就是 O(n^2k) 的了。

// Problem: Estimation
// Contest: SPOJ - Classical
// URL: https://www.spoj.com/problems/EST/
// Memory Limit: 1536 MB
// Time Limit: 6000 ms
// Author: Binah_cyc

#include<bits/stdc++.h>
using namespace std;
// #define int long long
bool startmb;
constexpr int N=2e3+5;
int n,k,a[N];

int dp[N][30][N],cyc[N][30];

int read()
{
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)) f=c=='-'?-1:f,c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    return x*f;
}

bool endmb;
main()
{
    cerr<<((&endmb-&startmb)/1024.0/1024);
    cin.tie(0)->sync_with_stdio(false);
    while((n=read())&&(k=read()))
    {
        for(int i=1;i<=n;i++) a[i]=read();
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<=k&&j<=i;j++)
            {
                for(int k=1;k<=n;k++) dp[i][j][k]=0x3f3f3f3f;
                cyc[i][j]=0x3f3f3f3f;
            }
        }
        for(int i=1;i<=n;i++) dp[0][0][i]=0;
        cyc[0][0]=0;
        for(int i=1;i<=n;i++) for(int j=1;j<=k&&j<=i;j++) for(int k=1;k<=n;k++) dp[i][j][k]=min(dp[i-1][j][k],cyc[i-1][j-1])+abs(a[i]-a[k]),cyc[i][j]=min(cyc[i][j],dp[i][j][k]);
        int ans=INT_MAX;
        for(int i=1;i<=k;i++) ans=min(ans,cyc[n][i]);
        cout<<ans<<'\n';
    }
    return 0;
}