#include<bits/stdc++.h>
using namespace std;
long long dis[1001],f[1001][1001],g[1001],x,y,a[1001][1001],n,m,q[1001];
int ysl(int k)
{
    return dis[k]+k*k-f[g[k]][k];
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>x>>y;
        cin>>a[x][y];
    }
    f[1][1]=a[1][1];
    g[1]=1;
    a[1][1]=0;
    for(int i=1;i<=m;i++)
    {
        int head=1;
        int tail=0;
        q[0]=0;
        for(int j=1;j<=m;j++)
        {
            if(g[j]==0)
            {
                dis[j]=0;
            }
            else dis[j]=(i-g[j])*(i-g[j]);
        }
        for(int j=1;j<=m;j++)
        {
            if(g[j])
               {
                    while(head<tail&&((ysl(q[tail])-ysl(q[tail-1]))*(j-q[tail])>=(ysl(j)-ysl(q[tail]))*(q[tail]-q[tail-1])))tail--;
                q[++tail]=j;
               }
            if(!a[i][j])continue;
            while(head<tail&&(((ysl(q[head+1]))-ysl(q[head]))<=2*j*(q[head+1]-q[head])))
                head++;
                int k=q[head];
                g[j]=i;
                dis[j]=0;
            f[i][j]=f[g[k]][k]-(i-g[k])*(i-g[k])-(j-k)*(j-k)+a[i][j];
                while(head<tail&&((ysl(q[tail])-ysl(q[tail-1]))*(j-q[tail])>=(ysl(j)-ysl(q[tail]))*(q[tail]-q[tail-1])))tail--;
                q[++tail]=j;
        }
    }
    cout<<f[m][m];
}

大佬求求了。 萌新刚学斜率优化DP，可以推荐几道题目吗