题解归档 - cf321E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf321E
• 本地来源：problems/cf321E/idea.md
• 题目链接：https://codeforces.com/contest/321/problem/E
• 原始标题：CF321E Ciel and Gondolas

思路

CF321E Ciel and Gondolas

题意

$n$ 人按 $1\ldots n$ 排成一队，要分成恰好 $k$ 个连续车厢，每节人数 $q_i>0$，$\sum q_i=n$。

矩阵 $u_{ij}=u_{ji}$（$0\le u_{ij}\le 9$）表示 $i,j$ 同车厢时的不友好度；一节车厢的不友好度为车内所有无序对的 $u_{ij}$ 之和。求总不友好度最小值。

做法

区间代价

令 $w(l,r)$ 为把 $[l,r]$ 放进同一车厢的代价。用二维前缀和 $s$：

$$w(l,r)=\frac{s[r][r]-s[l-1][r]-s[r][l-1]+s[l-1][l-1]}{2}$$

（矩形内所有 $u_{ij}$ 之和，对角为 0，每对被算两次故除以 2。）

DP

$f[g][i]$：前 $i$ 个人分成 $g$ 节车厢的最小代价。

$$f[g][i]=\min_{p< i} f[g-1][p]+w(p+1,i),\quad p\ge g-1$$

朴素 $O(n^2k)$ 会 TLE。

四边形不等式 + 决策单调性

$u_{ij}\ge 0$ 时区间代价满足四边形不等式，最优决策点 $\mathrm{opt}[g][i]$ 对固定 $g$ 关于 $i$ 单调，从而有

$$\mathrm{opt}[g-1][i]\le \mathrm{opt}[g][i]\le \mathrm{opt}[g][i+1]$$

枚举 $p$ 时只需在缩窄后的区间里转移，总复杂度 $O(nk)$（$n\le 4000,k\le 800$ 可过）。

实现注意

• 快读（fread）避免 I/O TLE。
• 初始化 $\mathrm{opt}[0][i]=0$，$\mathrm{opt}[g][n+1]=n$。

验证

• 样例 1/2/3 输出 $0/7/2$。
• WSL 对拍 brute（$n\le 80$ 朴素 DP）200 组通过（Kali 暂不可达时用 tools/stress_wsl.py）。

复杂度

• 时间：$O(n^2+nk)$
• 空间：$O(n^2)$

代码

来源：problems/cf321E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 05:02:15
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=4005;
const ll maxk=805;
const ll inf=1e18;
ll n,k,a[maxn][maxn],p[maxn][maxn],c[maxn][maxn],dp[maxk][maxn];
inline ll read(){
    ll zc=0,pd=1;
    char ch=getchar();
    while(ch<'0' or ch>'9'){
        if(ch=='-') pd=-1;
        ch=getchar();
    }
    while(ch>='0' and ch<='9'){
        zc=zc*10+ch-'0';
        ch=getchar();
    }
    return zc*pd;
}
void compute(ll car,ll L,ll R,ll optL,ll optR){
    ll M=(L+R)>>1,cur=inf,dq=optL,i,zc;
    for(i=optL;i<=optRandi<M;i++){
        zc=dp[car-1][i]+c[i+1][M];
        if(zc<cur) cur=zc,dq=i;
    }
    dp[car][M]=cur;
    if(L<R){
        compute(car,L,M-1,optL,dq);
        compute(car,M+1,R,dq,optR);
    }
}
int main(){
    ll i,j;
    n=read(); k=read();
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            a[i][j]=read();
    for(i=1;i<=n;i++){
        p[i][0]=0;
        for(j=1;j<=n;j++) p[i][j]=p[i][j-1]+a[i][j];
    }
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
            c[i][j]=c[i][j-1]+p[j][j]-p[j][i-1];
    for(i=0;i<=k;i++)
        for(j=0;j<=n;j++)
            dp[i][j]=inf;
    dp[0][0]=0;
    for(i=1;i<=k;i++) compute(i,1,n,0,n-1);
    cout<<dp[k][n]<<"\n";
    return 0;
}