[Codeforces 321E]Ciel and Gondolas (中文：搭車問題)

首先，我們可以設計一個$DP$，$DP[c][p]$代表將前$p$個人分配到$c$台車的最小花費 (即：陌生程度總合)

為了方便說明，定義$COST[i][j]$為將第$i$個人到第$j$個人塞進同一台車的花費
全部的$COST[i][j]$可以$O(N^{2})$預處理出來

因此我們有$DP[c][p]=min(DP[c-1][k]+COST[k+1][p])$，為了將明顯多餘的情況篩除，限制$c-1\leq k\leq p-1$
邊界條件：$DP[1][p]=COST[1][p]$
直接枚舉的時間複雜度是$O(N^{2}K)$

怎麼優化呢？

有一個滿直觀但是我不會證明的現象：(出題者說可以用high school algebra證明......求幫助......)
2016/2/22更新：我已成功自行證明此性質，請參考這裡
對於任意的$c$ ($c\geq 2$)：

令$k_{p}$是第一個讓$DP[c-1][k]+COST[k+1][p]=DP[c][p]$的$k$
我們有$k_{c}\leq k_{c+1}\leq k_{c+2}\leq ...\leq k_{N}$

因此，如果我們知道了$k_{p}$，就知道$k_{c}\sim k_{p-1}\leq k_{p}\leq k_{p+1}\sim k_{N}$
廢話(?
請別小看它，因為這樣代表了要求出$k_{p_{smaller}}$ ($p_{smaller}<p$)，我們只需要枚舉$\leq k_{p}$的$k$就好；要求出$k_{p_{larger}}$ ($p_{larger}>p$)，我們只需要枚舉$\geq k_{p}$的$k$就好

假如$p$ ($k_{p}$則不一定) 剛好取中間的話，計算量會減少一半！

如果我們像這樣一直二分區間，直到剩下一個元素為止，時間複雜度好像還滿開心的(?)
仔細想想，二分最多$O(\log N)$層，每一層最多枚舉$2N$個$k$，因此時間複雜度$O(N\log N)$
這是計算某個$c$的情況

總時間複雜度：$O(N^{2}+KN\log N)$ (別忘了還有$COST$的預處理)

p.s.這個code並不能直接AC，需要做深度優化，優化後的code在這裡

code:

#include<cstdio>
#include<cassert>
using namespace std;
const int INF=2147483647;
int N,K,GRID[4001][4001];
int COST[4001][4001];
void Build_COST()
{
    static int sum[4001][4001];//sum[i][j]=GRID[1][j]+GRID[2][j]+...+GRID[i][j]
    for(int i=1;i<=N;i++)assert(GRID[i][i]==0);
    for(int j=1;j<=N;j++)for(int i=1;i<=j;i++)sum[i][j]=sum[i-1][j]+GRID[i][j];
    for(int i=1;i<=N;i++)
    {
        COST[i][i]=0;
        for(int j=i+1;j<=N;j++)
        {
            COST[i][j]=COST[i][j-1]+(sum[j][j]-sum[i-1][j]);
        }
    }
}
int GetBestPeople(const int *pre,const int sum,const int min_people,const int max_people)
{
    assert(min_people<=max_people);
//    printf("sum=%d,min_people=%d,max_people=%d\n",sum,min_people,max_people);
    int mn=INF,ans=-1;
    for(int people=min_people;people<=max_people;people++)
    {
        if(pre[people-1]+COST[people][sum]<mn)mn=pre[people-1]+COST[people][sum],ans=people;
    }
    assert(ans!=-1);
    return ans;
}
void Query(const int *pre,int *ans,const int left_sum,const int right_sum,const int min_people,const int max_people)
{
    if(left_sum>right_sum)return;
    const int mid_sum=(left_sum+right_sum)/2;
    const int best_people=GetBestPeople(pre,mid_sum,min_people,max_people);
    ans[mid_sum]=pre[best_people-1]+COST[best_people][mid_sum];
    Query(pre,ans,left_sum,mid_sum-1,min_people,best_people);
    Query(pre,ans,mid_sum+1,right_sum,best_people,max_people);
}
int DP[801][4001];//DP[i][j]=i cars contain j people
int Solve()
{
    if(K>=N)return 0;//one people one car
    for(int i=1;i<=N;i++)DP[1][i]=COST[1][i];
    for(int cars=2;cars<=K;cars++)
    {
        Query(DP[cars-1],DP[cars],cars,N,cars,N);
        assert(DP[cars][cars]==0);
    }
    return DP[K][N];
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&K)==2)
    {
        for(int i=1;i<=N;i++)for(int j=1;j<=N;j++)scanf("%d",&GRID[i][j]);
        Build_COST();
        printf("%d\n",Solve());
    }
    return 0;
}