CF321E - Ciel and Gondolas

考虑 \(dp_{i,j}\) 表示用 \(i\) 条船载走前 \(j\) 个人的最小贡献，\(w_{i,j}\) 表示区间 \([i,j]\) 里的人同乘一条船的代价。则 \(dp_{i,j}=\min_{1\le k\lt j}(dp_{i-1,k}+w_{k+1,j})\)。

我们发现，\(w_{i,j}\) 可以通过 \(w_{i,j-1}+s_{j,j}-s_{j,i-1}\) 递推计算。其中 \(s_{i,j}\) 是第 \(i\) 行前 \(j\) 个的和。简而言之就是往 \([i,j-1]\) 里面加入 \(j\) 和 \([i,j]\) 产生的贡献，复杂度 \(O(n^2)\)。

然后考虑 \(w_{i,j}\) 的性质。首先它是满足包含单调性的，因为加入一个数的代价一定是正的。然后考虑它是否满足四边形不等式。如果我们把序列分成三块 \(A,B,C\)，我们只需要证明 \(w_{A\cup B}+w_{B\cup C}\le w_B+w_{A\cup B\cup C}\) 即可。我们发现，记 \(f_{A,B}\) 表示集合 \(A\) 中的数和集合 \(B\) 中的数的贡献，则原式等于 \(f_{A,A}+f_{A,B}+f_{B,B}+f_{B,B}+f_{B,C}+f_{C,C}\le f_{B,B}+f_{A,A}+f_{A,B}+f_{B,B}+f_{C,C}+f_{B,C}+f_{A,C}\)

我们整理一下发现，变成了 \(0\le f_{A,C}\)，显然是成立的，所以 \(w_{i,j}\) 满足四边形不等式。

那么我们就套用四边形不等式的第二个形式，决策点满足 \(k_{i-1,j}\le k_{i,j}\le k_{i,j+1}\)，可以证明总复杂度 \(O(n^2)\)，常数略大。

int n,k,u[4005][4005];
int s[4005][4005];
int w[4005][4005];
int dp[805][4005];
int m[805][4005];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>k;
	rp(i,n)rp(j,n)cin>>u[i][j];
	rp(i,n)rp(j,n)s[i][j]=s[i][j-1]+u[i][j];
	rp(l,n)rep(r,l+1,n){
		w[l][r]=w[l][r-1]+(s[r][r]-s[r][l-1]);
	}rep(j,1,n)dp[0][j]=1e9; 
	rep(i,1,k)per(j,1,n){
		dp[i][j]=1e9;
		rep(s,m[i-1][j],(j==n?n:m[i][j+1])){
			if(dp[i][j]>dp[i-1][s]+w[s+1][j]){
				dp[i][j]=w[s+1][j]+dp[i-1][s];
				m[i][j]=s;
			}
		}
	}cout<<dp[k][n]<<endl;
	return 0;
}
//Nyn-siyn-hert