20140816

2840 단어
A.DP에 관해서는 배울 가치가 있으니 추이 과정에 대해 잘 생각해 보세요 화이팅!제목 대의: (0,0)에서 (n,m)까지는 오른쪽이나 아래로만 갈 수 있고 처음에는 에너지 1이 있습니다. 어떤 점에 도달하면 가중치가 0보다 크다는 것을 보증합니다. 최소 에너지를 얼마나 더 넣어야 하는지/Magic Grid 분석: 검색도 가능하고 DP 코드도 가능합니다.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

const int maxn = 500+10;
const int inf = 99999;

int T, r, c, ans;
int f[maxn][maxn], s[maxn][maxn];

int dp(int x, int y)
{    
    if(x > r || y > c)    return inf;
    if(f[x][y] != inf)    return f[x][y];
    return    f[x][y] = min(max(dp(x+1, y)-s[x][y], 1), max(dp(x, y+1)-s[x][y], 1));
}

int main()
{
    cin >> T;
    while(T--) {
        cin >> r >> c;
        for(int i = 1; i <= r; i++)
            for(int j = 1; j <= c; j++)
                f[i][j] = inf;
        f[r][c] = 1;
        for(int i = 1; i <= r; i++)
            for(int j = 1; j <= c; j++)
                scanf("%d", s[i][j]);
        cout << dp(1, 1) << endl;
    }
    return 0;
}

좋은 웹페이지 즐겨찾기