分析一下样例就可以知道，求的实际上是从左下角到右上角的最长路

因为对于任意不在这个最长路的上的点，都可以通过经过最长路上的点的路径将这个点的价值减光

(可以用反证法证明)

之后就是一个非常NOIP的DP了

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std; const int maxn=1010;int T,n,m;int f[maxn][maxn];int map[maxn][maxn];void cmax(int &a,int b){if(a
          
           ='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();} int main(){ read(T); while(T--){ read(n);read(m); for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)read(map[i][j]); memset(f,0,sizeof(f)); for(int i=n;i>=1;--i){ for(int j=1;j<=m;++j){ cmax(f[i][j],f[i+1][j]); cmax(f[i][j],f[i][j-1]); cmax(f[i][j],f[i+1][j-1]+map[i][j]); } }printf("%d\n",f[1][m]); }return 0;}