TJOI2015
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 i = 1; i <=n; ++ i)
{
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;
* -----------------------------------------------------------------
* 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 i = 1; i <=n; ++ i)
{
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;
