组合数学 - BZOJ 3997 - TJOI2015TJOI2015 Problem's Link

 ----------------------------------------------------------------------------

Mean: 

N×M的网格，一开始在(1,1)每次可以向下和向右走，每经过一个有数字的点最多能将数字减1，最终走到(N,M).

问至少要走多少次才能将数字全部变为0 （N,M<=1000,ai,j<=106）

analyse:

结论题.

设d(i,j)

d(i,j)=max(d(i−1,j),d(i,j+1),d(i−1,j+1))+a[i,j]

答案是d(n,1)

Time complexity: O(N)

view code

/**

* -----------------------------------------------------------------

* Copyright (c) 2016 crazyacking.All rights reserved.

*       Author: crazyacking

*       Date  : 2016-02-15-13.19

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long(LL);

typedef unsigned long long(ULL);

const double eps(1e-8);

typedef long long ll;

ll d[1005][1005];

int main()

{

   int T;

   scanf("%d", &T);

   while(T--)

   {

       int n, m;

       scanf("%d%d", &n, &m);

       for(int i=1; i<=n; ++i)

       {

           for(int j=1; j<=m; ++j)

           {

               scanf("%lld", &d[i][j]);

           }

       }

           for(int j=m; j>=1; --j)

               d[i][j]=max(d[i][j]+d[i-1][j+1], max(d[i][j+1], d[i-1][j]));

       printf("%lld\n", d[n][1]);

   }

   return 0;