【2019.8.8 慈溪模拟赛 T1】开箱（chest）（暴力DP水过）

转化题意

这题目乍一看十分玄学，完全不可做。

但实际上，假设我们在原序列从小到大排序之后，选择开的宝箱编号是\(p_{1\sim Z}\)，则最终答案就是：

\[\sum_{i=1}^Za_{p_i}(p_{i+1}-p_i)
\]

其中\(p_{Z+1}=n+1\)。

有了这个式子，就可做了许多。

暴力\(DP\)

我们设\(f_{i,j}\)为在前\(i\)个宝箱中选择了\(j\)个宝箱的最小代价。

枚举一个转移点\(k\)表示上个选择的宝箱，就可以得到：

\[f_{i,j}=f_{k,j-1}+(a_k-a_i)(n-i+1)
\]

这虽然是\(O(n^3)\)的，但\(n\)才\(1000\)，加上其常数很小，实际实现中又可以将枚举时除以个\(8\)，所以能跑过。

斜率优化

比赛时调了一个多小时没调出来。。。加上暴力\(DP\)能过，就没再想了。。。

这里先占个坑吧。

代码（暴力\(DP\)）

#include<bits/stdc++.h>

#define Tp template<typename Ty>

#define Ts template<typename Ty,typename... Ar>

#define Reg register

#define RI Reg int

#define Con const

#define CI Con int&

#define I inline

#define W while

#define N 1000

#define INF 2e9

#define LL long long

#define min(x,y) ((x)<(y)?(x):(y))

#define Gmin(x,y) (x>(y)&&(x=(y)))

using namespace std;

int n,m,a[N+5];

class BruteForceSolver

{

	private:

		int f[N+5][N+5];

	public:

		I void Solve()

		{

			RI i,j,k;for(i=0;i<=n;++i) for(j=0;j<=m;++j) f[i][j]=INF;//初始化

			for(f[0][0]=0,j=1;j<=m;++j) for(i=j;i<=n;++i)//枚举i,j

				for(k=j-1;k^i;++k) Gmin(f[i][j],f[k][j-1]+1LL*(a[i]-a[k])*(n-i+1));//枚举转移点k进行转移

			RI ans=INF;for(i=0;i<=n;++i) Gmin(ans,f[i][m]);printf("%d",ans);//求答案

		}

}B;

int main()

{

	freopen("chest.in","r",stdin),freopen("chest.out","w",stdout);

	RI i;for(scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",a+i);sort(a+1,a+n+1);//注意排序

	return B.Solve(),0;

}

巴特西

【2019.8.8 慈溪模拟赛 T1】开箱（chest）（暴力DP水过）

转化题意

暴力\(DP\)

斜率优化

代码（暴力\(DP\)）

最新文章

热门文章