做题时间：2022.10.18
\(【题目描述】\)
有 \(n(n\leq 4000)\) 个人按 \(1\rightarrow n\) 编号，并按这个顺序站成一排，现在要将他们分成连续的 \(k(k\leq \min(n,800))\)组，对于任意不相同的人 \(i,j\)，若他们分在一组，则会产生 \(p_{i,j}(0\leq p_{i,j}\leq 9)\) 的沮丧值（保证 \(p_{i,i}=0\)），现要求最小的沮丧值之和。
\(【输入格式】\)
第一行两个整数 \(n,k\)
接下来 \(n\) 行每行 \(n\) 个整数表示 \(p_{i,j}\)
\(【输出格式】\)
一行一个整数表示答案
\(【考点】\)
决策单调性优化dp
\(【做法】\)
设 \(f_{i,j}\) 表示前 \(i\) 个人分成 \(j\) 组的最小沮丧值之和。有：
\[f_{i,j}=\min(f_{k-1,j-1}+\sum\limits_{a=k}^{i}\sum\limits_{b=k}^i p_{i,j}) \]由于 \(p_{i,j}\geq 0\)，因此肯定满足决策单调性和四边形不等式，这种2D/1D的转移方程，可以直接进行分治，复杂度 \(O(nk\log n)\)，也可以使用四边形不等式优化，记录决策点减少枚举复杂度，复杂度 \(O(nk)\)
\(【代码】\)
分治：
#include<cstdio>
#include<iomanip>
#include<cstring>
using namespace std;
const int N=4e3+50,M=805;
int f[N][M],n,k;
int sum[N][N],p[N][N];
inline int Read()
{
int x=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)){
x=(x<<1)+(x<<3)+ch-48;
ch=getchar();
}
return x;
}
int val(int l,int r)
{
return sum[r][r]-sum[l-1][r]-sum[r][l-1]+sum[l-1][l-1];
}
void dp(int l,int r,int jl,int jr,int cur)
{
if(l>r) return ;
int mid=(l+r)>>1;
int num=0;
for(int k=jl;k<=min(jr,mid);k++){
int t=f[k-1][cur-1]+val(k,mid);
if(t<f[mid][cur]){
f[mid][cur]=t;
num=k;
}
}
dp(l,mid-1,jl,num,cur);
dp(mid+1,r,num,jr,cur);
}
void pre()
{
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+p[i][j];
}
}
}
int main()
{
n=Read(),k=Read();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) p[i][j]=Read();
}
pre();
memset(f,0x3f3f3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=k;i++) dp(1,n,1,n,i);
printf("%d\n",f[n][k]/2);
return 0;
}
四边形不等式优化：
#include<cstdio>
#include<iomanip>
#include<cstring>
using namespace std;
const int N=4e3+50,M=805;
int f[M][N],n,k;
int sum[N][N],p[N][N],m[N][N];
inline int Read()
{
int x=0;
char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)){
x=(x<<1)+(x<<3)+ch-48;
ch=getchar();
}
return x;
}
int val(int l,int r)
{
return sum[r][r]-sum[l-1][r]-sum[r][l-1]+sum[l-1][l-1];
}
void pre()
{
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+p[i][j];
}
}
}
int main()
{
n=Read(),k=Read();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++) p[i][j]=Read();
}
pre();
memset(f,0x3f3f3f,sizeof f);
f[0][0]=0;
for(int i=1;i<=n;i++) m[0][i]=1,m[i][n+1]=n;
for(int i=1;i<=k;i++){
for(int j=n;j>=1;j--){
for(int k=m[i-1][j];k<=m[i][j+1];k++){
int t=f[i-1][k-1]+val(k,j);
if(t<f[i][j]) f[i][j]=t,m[i][j]=k;
}
}
}
printf("%d\n",f[k][n]/2);
return 0;
}