UVALive 5983 MAGRID

题意：在一个n*m的网格上，从(0,0)走到(n-1,m-1)，每次只能向右或者向下走一格。一个人最初有一个生命值x，走到每一个格生命值会变为x + s[i][j]，(s[i][j]可为负，0，正)，若生命值小于等于0，则人死亡。告诉网格上所有s[i][j]，求x的最小值使得该人能够或者走到(n-1,m-1)。|s[i][j]| < 1000，n,m < 500。

解法：这道题不能直接dp，否则会错。必须要先二分x的值，然后再dp。dp[i][j]记录的是走到(i,j)格所能有的最大生命值，但是要注意，d[i][j]只能在d[i][j-1]或d[i-1][j]中有一个为正时才能转移过来。

　　　if (d[i-1][j] > 0) d[i][j] = max(d[i][j], d[i-1][j] + s[i][j])， if (d[i][j-1] > 0) d[i][j] = max(d[i][j], d[i][j-1] + s[i][j])。初始化时将所有d[i][j]赋值为-1。

tag:二分，dp

 /*
  * Author:  Plumrain
  * Created Time:  2013-12-03 20:25
  * File Name: DP-LA-5983.cpp
  */
 #include <iostream>
 #include <cstdio>
 #include <cstring> using namespace std; #define CLR(x) memset(x, 0, sizeof(x))
 #define CLR1(x) memset(x, -1, sizeof(x)) int n, m;
 int d[][];
 int s[][]; void init()
 {
     scanf ("%d%d", &n, &m);
     for (int i = ; i < n; ++ i)
         for (int j = ; j < m; ++ j)
             scanf ("%d", &s[i][j]);
 } bool dp(int x)
 {
     CLR1 (d);
     d[][] = x + s[][];
     for (int i = ; i < n; ++ i)
         if (d[i-][] > )
             d[i][] = d[i-][] + s[i][];
     for (int i = ; i < m; ++ i)
         if (d[][i-] > )
             d[][i] = d[][i-] + s[][i];     for (int i = ; i < n; ++ i)
         for (int j = ; j < m; ++ j){
             if (d[i][j-] > )
                 d[i][j] = max(d[i][j], d[i][j-] + s[i][j]);
             if (d[i-][j] > )
                 d[i][j] = max(d[i][j], d[i-][j] + s[i][j]);
         }
     if (d[n-][m-] <= ) return ;
     return ;
 } int bin_search()
 {
     int l = , r = 1e7;
     while (l <= r){
         int mid = (l + r) >> ;
         if (!dp(mid)) l = mid + ;
         else r = mid - ;
     }
     return l;
 } int main()
 {
     int T;
     scanf ("%d", &T);
     while (T--){
         init();
         int ans = bin_search();
         printf ("%d\n", ans);
     }
     return ;
 }