codeforces 321E Ciel and Gondolas 四邊形不等式

codeforces 321E Ciel and Gondolas 四邊形不等式

題目大意：給定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<