[Codeforces Round #190 (Div. 1)][DP] Ciel and Gondolas

原題連結
這題的重點在於DP優化中決策點的單調性，有許多性質還是需要參考論文和證明才能懂的
有關於決策點的說明可以參考一下官方題解

#define LL long long
#include<bits/stdc++.h>
using namespace std;
const LL maxn=4000+5;
const LL maxk=800+5;
const LL INF=(1LL<<60);
LL cost[maxn][maxn],c[maxn][maxn],pre[maxn][maxn];
LL dp[maxk][maxn];
inline LL readint()
{
    LL ret=0;
    char c;
    for(;;)
    {
        c=getchar();
        if(c=='\n' || c==' ') return ret;
        ret=ret*10+c-'0';
    }
}
void compute(LL car,LL L,LL R,LL optL,LL optR)
{
    LL M=L+(R-L)/2,opt=-1; // cal dp[car][M] first
    dp[car][M]=INF;
    for(LL i=optL;i<=optR;i++) if(dp[car][M]>dp[car-1][i]+cost[i+1][M]) 
        dp[car][M]=dp[car-1][i]+cost[i+1][M],opt=i;
    if(L>=R) return;
    compute(car,L,M-1,optL,opt);
    compute(car,M+1,R,opt,optR);
}
int main()
{
    LL n,k;
    n=readint();k=readint();
    for(LL i=1;i<=n;i++)
    {
        pre[i][0]=0;
        for(LL j=1;j<=n;j++)
        {
            c[i][j]=readint();
            pre[i][j]=pre[i][j-1]+c[i][j];
        }
    }
    for(LL i=1;i<=n;i++) for(LL j=i;j<=n;j++) cost[i][j]=cost[i][j-1]+pre[j][j]-pre[j][i-1];
    for(LL j=1;j<=n;j++) dp[1][j]=cost[1][j];
    for(LL i=2;i<=k;i++) compute(i,1,n,1,n);
    printf("%lld\n",dp[k][n]);
}