想了很久都想不出怎么dp，然后发现有些例子，如果你开始不确定起始值的话，是不能dp的，每种状态都有可能，所以只能二分一个答案，确定开始的val值，来dp了。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn=500+20; LL dp[maxn][maxn]; int n,m; int a[maxn][maxn]; bool check (LL val) { dp[1][1]=val; for (int i=1;i<=n;++i) { for (int j=1;j<=m;++j) { if (i==1 && j==1)continue; if (dp[i-1][j]<=0) dp[i-1][j]=-inf; //如果小于0，证明已经不能走了 if (dp[i][j-1]<=0) dp[i][j-1]=-inf; if (dp[i-1][j]<=0 && dp[i][j-1]<=0) dp[i][j]=-inf; else dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j]; } } return dp[n][m]>0; } void work () { scanf("%d%d",&n,&m); for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) scanf("%d",&a[i][j]); LL begin=1,end=1LL*500*500*1000+20; while (begin<=end) { LL mid = (begin+end)>>1; //printf ("%d ",mid); if (check(mid)) end=mid-1; else begin=mid+1; } printf ("%lld ",begin); //check(998); //check(3); //printf ("%d ",check(1002)); // printf ("%lld ",dp[2][4]); return ; } int main() { #ifdef local freopen("data.txt","r",stdin); #endif for (int i=1;i<=500;++i) { dp[0][i]=-inf; dp[i][0]=-inf; } dp[0][0]=-inf; dp[0][1]=0; dp[1][0]=0; int t; scanf("%d",&t); while (t--) work(); return 0; }