代码记得加上快读,注意卡常. 否则AC变成TLE40多个点 这里对应的是luogu的题解2代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define inf 0x3f3f3f3f
#define R register
using namespace std;
const int N=4010;
inline int read()
{
  R int x=0,f=1; char c=getchar();
  while(!isdigit(c)){ if(c=='-') f=-1; c=getchar();}
  while(isdigit(c))
  {
    x=(x<<3)+(x<<1)+(c^48);
	c=getchar();
  }
  return x*f;
}
inline void write(int x)
{
  if(!x) putchar('0');
  if(x<0) putchar('-'),x=-x;
  R int tot=0;
  static int re[26];
  while(x) re[tot++]=x%10,x/=10;
  while(tot) putchar(re[--tot]+48);
}
int n,w[N][N],dp[N][N],dis[N][N],ke[N][N],d[N][N],g;
inline void init()
{
  for(R int i=n;i>=1;i--)
  {
    dis[i][i]=w[i][i];
    for(R int j=i+1;j<=n;j++)
	  dis[i][j]=dis[i+1][j]+ke[i][j];
  }
}
int main()
{
  n=read(); g=read();
  for(R int i=1;i<=n;i++)
    for(R int j=1;j<=n;j++)
	{
	  w[i][j]=read();
	  if(j<=i) continue;
	  ke[i][j]=ke[i][j-1]+w[i][j];
	}
  init();
  memset(dp,0x3f,sizeof(dp));
  dp[0][0]=0;
  for(R int j=1;j<=g;j++)
  {
    d[n+1][j]=n;
	for(R int i=n;i>=1;i--)
	{
	  int minn=inf,mi;
	  for(R int k=d[i][j-1];k<=d[i+1][j];k++)
	    if(dp[k][j-1]+dis[k+1][i]<minn)
		{
		  minn=dp[k][j-1]+dis[k+1][i];
		  mi=k;
		}
	  dp[i][j]=minn;
	  d[i][j]=mi;
	}
  }
  write(dp[n][g]);
  return 0;
}