P6304 题解

简单带优化 dp，建议黄。

思路

本题的另一道原题为 CF1012C。

设 $f_{i,j}$ 为目前到 $i$，放了 $j$ 个，且当前放了的最小总代价，不考虑山 $i+1$ 造成的代价，$v(i)(i<n)$ 表示将 $a_{i+1}$ 减小至不大于 $a_i$，则转移为

$$f_{i,j}= \begin{cases} 0 & i=1,j=1\\ v(i-1) & i>1,j=1\\ \min(\min\limits_{k=1}^{i-2}[f_{k,j-1}+v(k)],f_{i-2,j-1}+\max(v(i-2),v(i-1))) & i>1,j>1\\ \end{cases}$$

建 $i$ 栋房的答案即为 $\min\limits_{j=\lceil\frac{i}{2}\rceil}^{n}(f_{j,i}+v(j)\times[j\neq n])$，总复杂度为 $O(n^3)$。这个方括号是什么？

显然可以定义 $g_{i,j}$ 表示 $\min\limits_{k=1}^{i}[f_{k,j}+v(k)]$，即可做到 $O(n^2)$。

Code

少数变量名和上文有出入。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[5005],dp[5005][5005],f[5005][5005],ans[5005];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n ;
	for(int i=1;i<=n;i++) cin >> a[i] ;
	memset(dp,0x3f,sizeof(dp));
	memset(f,0x3f,sizeof(f));
	memset(ans,0x3f,sizeof(ans));
	for(int i=1;i<=n;i++){
		for(int j=1;j*2-1<=i;j++){
			if(i==1){
				if(j==1) dp[i][j]=0;
			}else{
				if(j==1) dp[i][j]=max(0ll,a[i-1]-a[i]+1);
				else dp[i][j]=min(f[i-2][j-1]+max(0ll,a[i-1]-a[i]+1),dp[i-2][j-1]+max({0ll,a[i-1]-a[i]+1,a[i-1]-a[i-2]+1}));
			}f[i][j]=min(f[i-1][j],dp[i][j]+max(0ll,a[i+1]-a[i]+1));
			ans[j]=min(ans[j],dp[i][j]+(i==n ? 0 : max(0ll,a[i+1]-a[i]+1)));
		}
	}for(int i=1;i*2-1<=n;i++) cout << ans[i] << " " ;
	return 0;
}

感谢阅读。