题解：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)

的了。

CPP

// 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;
}

题解：SP16809 EST - Estimation

文章操作

相关推荐

评论

题解：SP16809 EST - Estimation