题目大意：给定 n 个人，需要分 k 次过河，两个人 i,j 如果同乘一条船就会产生 ai,j 的代价，求最终代价的最小值

这个玩应显然满足四边形不等式(虽然我并不知道这个不等式是啥
然后就是决策单调(虽然我并不知道为何满足四边形不等式一定决策单调
然后就能分治做辣。。。
定义 Solve(l,r,optl,optr) 表示当前在处理区间 [l,r] ，最优决策区间为 [optl,optr]
然后我们用区间 [optl,min(optr,mid?1)] 的 f 值来更新 f[mid] ，并记录最优决策点 pos
那么 [l,mid?1] 部分的最优决策一定在 [optl,pos] ， [mid+1,r] 部分的最优决策一定在 [pos,optr]
递归做下去就行了，时间复杂度 O(nlogn)
做 k 次即可

注意这题不加读入优化会T掉。。。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #define M 4040 using namespace std; int n,k; int a[M][M],f[880][M]; int Sum(int x,int y) { return a[y][y]+a[x-1][x-1]-a[x-1][y]-a[y][x-1]; } void Solve(int f[],int g[],int l,int r,int opt_l,int opt_r) { if(l>r) return ; int i,mid=l+r>>1,pos=opt_l; g[mid]=0x3f3f3f3f; for(i=opt_l;i<=min(opt_r,mid-1);i++) if(f[i]+Sum(i+1,mid)
       
        '9' ) c=Get_Char(); return c-'0'; } } int main() { //freopen("321E.in","r",stdin); //freopen("321E.out","w",stdout); int i,j; cin>>n>>k; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { a[i][j]=IStream::Get_Int()+a[i-1][j]+a[i][j-1]-a[i-1][j-1]; } for(i=1;i<=n;i++) f[1][i]=Sum(1,i); for(i=2;i<=k;i++) Solve(f[i-1],f[i],i,n,i-1,n-1); cout<