algorithm - 找到能提供最少能量的路径

Question

ACM 国际大学生编程竞赛，Asia-Amritapuri 网站，2011 年问题A:MAGRID

非常感谢您在 10 月份帮助哈利·波特找到永生魔法石。我们不是告诉你这只是一个网络游戏吗？呃!现在这是 Harry 真正的现场任务。给定一个具有 R 行和 C 列的 magrid S(魔术网格)。这个 magrid 中的每个牢房都有我们勇敢的英雄必须打败的匈牙利蜂龙，或者他的老师斯内普留给他的一瓶魔法药水。单元格 (i,j) 的一条龙带走了 |S[i][j]|他的力量点数，并且单元格 (i,j) 中的药水使哈利的力量增加 S[i][j]。如果他的力量在旅途中的任何时候下降到 0 或更少，Harry 就会死去，并且没有任何魔法石可以使他复活。

哈利从左上角的单元格 (1,1) 开始，魔法石在右下角的单元格 (R,C) 中。从单元格 (i,j) 开始，Harry 只能向下或向右移动一个单元格，即移动到单元格 (i+1,j) 或单元格 (i,j+1)，并且他不能移动到 magrid 之外。哈利在开始他的旅程之前已经使用魔法来确定哪个细胞包含什么，但缺乏基本的简单数学技能来确定他开始收集魔法石所需的最低力量。请再次帮助他。

Input (STDIN):

The first line contains the number of test cases T. T cases follow. Each test case consists of R C in the first line followed by the description of the grid in R lines, each containing C integers. Rows are numbered 1 to R from top to bottom and columns are numbered 1 to C from left to right. Cells with S[i][j] < 0 contain dragons, others contain magic potions.

Output (STDOUT):

Output T lines, one for each case containing the minimum strength Harry should start with from the cell (1,1) to have a positive strength through out his journey to the cell (R,C).

约束:

1 ≤ T ≤ 30
2 ≤ R, C ≤ 500
-103 ≤ S[i][j] ≤ 103
S[1][1] = S[R][C] = 0

时间限制:3 秒内存限制:64 MB示例输入:

3
2 3
0 1 -3
1 -2 0
2 2
0 1
2 0
3 4
0 -2 -3 1
-1 4 0 -2
1 -2 -3 0

示例输出:

2
1
2

解释:情况 1:如果 Harry 在单元格 (1,1) 中以强度 = 1 开始，则他无法在任何可能的路径中保持正强度。他最初至少需要 strength = 2。情况 2:请注意，从 (1,1) 开始，他至少需要 strength = 1。

我尝试用第一种方法查看所有路径并选择能量最少的路径

#include<iostream>
#include<algorithm>
#include<stack>
#include<cmath>
using namespace std;

int TT,R,C,S[500][500];
int energy_g;
//unsigned long int fact(int a);
int trace(int r,int c,int energy,int energy_r);
int main(void)
{

    cin>>TT;

    for(int i=1;i<=TT;i++)
    {
    cin>>R>>C;     
    for(int r=1;r<=R;r++)
         for(int c=1;c<=C;c++)
         {
             cin>>S[r][c];
         //cout<<S[r][c];   
         }
     energy_g=32000;
     trace(1,1,0,0);
     cout<<energy_g<<endl;
    }
    return 0;
}

int trace(int r,int c,int energy,int energy_r)
{
    if(r>R || c>C)
        return 0;
    energy += S[r][c];
    if(energy < 0)
    {
    energy_r+=abs(energy)+1 ;       
    energy+=abs(energy)+1;
    }


    else if(energy == 0){        
    energy_r +=1;   
    energy +=1;
     }

    if(r == R && c == C)
    {

    if(energy_r < energy_g)
            energy_g = energy_r;
        return 0;
    }
    trace(r,c+1,energy,energy_r);
    trace(r+1,c,energy,energy_r);
    return 0;
}

请帮助我进一步优化它，因为我知道我实现的方法花费的时间最短

Answer 1

这是我脑海中的一个解决方案。我们将使用非常常见的技巧——对答案进行二分查找。解决方案可以分为两部分:

1) 检查我们是否可以以 N 的健康水平完成旅程。这可以通过简单的动态规划来完成 - 让 dp[i][j] 成为我们的最大能量水平当我们进入单元格(i，j)时可以有。由于我们只能向下或向右移动，dp[i][j] 可以总结为 (i-1,j) 和 (i,j-1) 的最佳移动。如果级别低于 1，则将值设置为负无穷大，因为我们不能承受 Harry 的死亡:)(或者在执行 DP 步骤时添加检查以排除不可能的瓷砖)。 dp[0][0]是N和dp[i][0]，dp[0][i]可以正确计算离开。然后进行类似表格的填充。要可视化，请查看 http://www.cs.berkeley.edu/~vazirani/algorithms/chap6.pdf 的图 6.4。 .

2) 对答案进行二分查找。最初 left = 1 和 right = 2000000000(或其他合适的上限)- 它们是二进制搜索的左右边界。在二分搜索的每次迭代中，我们检查是否可以以 mid = (left+right)/2 的健康水平完成旅程，并递归到适当的一半。

这在实践中会很有效——每个 DP 步骤都需要 O(R*C) 时间，二分查找添加一个 log(2000000000) 因子，大约是 30。这应该没问题。

它可能只用 DP 就可以解决，但我现在看不出如何解决。