POJ #1042 Gone Fishing

I used DP instead of Greedy. But got WA on PoJ, though it passed all web-searched cases. Maybe I have to use Greedy.
BTW: a careless modification introduced an error, and it took me 1+ hours to debug. DETAILS
Sth. about this DP solution: dp[iLake][nCurrTotalTime + currentLakeTime] = dp[iLake - 1][nCurrTotalTime] + getFish(iLake, nCurrTotalTime, currentLakeTime);
Anyway, this is the first 2D DP problem I worked out :)
  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <memory.h>
  4 #include <vector>
  5 using namespace std;
  6 
  7 #define Max(a, b) (a) > (b) ? (a) : (b)
  8 #define MAX_LAKE 25
  9 #define MAX_TIME (16*12)
 10 
 11 //    We are at lake i now, with total time of tTtlLake spent on previous lakes, 
 12 //    and we'd like to spend myt time on lake i -> how many fishes we can get from lake i?
 13 int getFish(int i, int tTtlLake, int myt, int *accti, int *fi, int *di)
 14 {
 15     if (myt == 0) return 0;
 16 
 17     //    If any left, get fishes by time myt
 18     int ret = 0, left = fi[i];;
 19     while (left > 0 && myt > 0)
 20     {
 21         ret += left;
 22         left -= di[i];
 23         myt--;
 24     }
 25     return ret;
 26 }
 27 
 28 void backtrack(int path[MAX_LAKE + 1][MAX_TIME], int si, int sk, int n, int h)
 29 {
 30     bool bHasSolution = false;
 31     int opath[MAX_LAKE + 1] = { 0 };
 32     int actTtl = 0;
 33     while (si > 0 && path[si][sk] != -1)
 34     {
 35         opath[si] = path[si][sk];
 36         actTtl += opath[si];
 37         sk -= path[si][sk];
 38         si--;
 39         bHasSolution = true;
 40     }
 41     //    Actual results less than h?
 42     if (actTtl < h)
 43     {
 44         bool allAfterZero = true;
 45         for (int i = 2; i <= n; i++)
 46         {
 47             if (opath[i] != 0)
 48             {
 49                 allAfterZero = false;
 50             }
 51         }
 52         if (allAfterZero)
 53         {
 54             opath[1] += h - actTtl;
 55         }
 56     }
 57     if (!bHasSolution)
 58     {
 59         opath[1] = h;
 60     }
 61     for (int i = 1; i <= n; i++)
 62     {
 63         printf("%d", opath[i] * 5);
 64         if (i < n) printf(", ");
 65     }
 66     printf("
");
 67 }
 68 
 69 void calc(int n, int h, int *fi, int *di, int *ti, int *accti)
 70 {
 71     //    Reset
 72     int   dp[MAX_LAKE + 1][MAX_TIME];
 73     int path[MAX_LAKE + 1][MAX_TIME];
 74     memset(  dp, 0, sizeof(int) * MAX_TIME * (MAX_LAKE + 1));
 75     memset(path, -1, sizeof(int)* MAX_TIME * (MAX_LAKE + 1));
 76 
 77     //    dp[currentLakeIndex, currentTtlTimeOnLake]    = currTtlFishCnt. Note: no time on the way included
 78     //    dp[i + 1, tTtl + t] = dp[i, tTtl]  + f(fi(i + 1), t)
 79 
 80     int maxFish = 0, maxI, maxT;
 81     for (int i = 1; i <= n; i++)
 82     {
 83         // time on the way so far        
 84         int tWay = accti[i-1];
 85 
 86         for (int t = h; t >=0; t--)    // descending is necessary: it required more miniutes to spend as earlier as possible
 87         {
 88             if (i == 1 && t > 0) continue;
 89             
 90             int leftTime = h - t - tWay;
 91             leftTime = leftTime < 0 ? 0 : leftTime;
 92 
 93             for (int k = 0; k <= leftTime; k++) // k is how much time left in total
 94             {
 95                 int newV = dp[i - 1][t] + getFish(i, t, k, ti, fi, di);
 96                 if (newV > dp[i][t + k])
 97                 {
 98                     dp[i][t + k] = newV;                    
 99                     path[i][t + k] = k;
100                     //printf("-putting %d to [%d][%d]
", k, i, t + k);
101 
102                     if (newV > maxFish)
103                     {
104                         maxFish = newV;
105                         maxI = i; maxT = t + k;
106                     }                    
107                 }
108             }
109         }
110     }
111 
112     backtrack(path, maxI, maxT, n, h);
113      printf("Number of fish expected: %d

", maxFish);
114 }
115 
116 int main()
117 {
118     int n, h;    
119     while (scanf("%d", &n), (n != 0))
120     {    
121         scanf("%d", &h);
122 
123         // all in 5min-interval 
124         h *= 12;
125 
126         int fi[MAX_LAKE + 1] = { 0 };    //    initial fish cnt
127         int di[MAX_LAKE + 1] = { 0 };    //    decrease rate
128         int ti[MAX_LAKE]     = { 0 };    //    travel time
129         int accti[MAX_LAKE] = { 0 };    //    travel time
130 
131         //    Get Input            
132         for (int i = 1; i <= n; i ++)    scanf("%d", fi + i);
133         for (int i = 1; i <= n; i ++)    scanf("%d", di + i);
134         for (int i = 1; i <= n - 1; i++)
135         {
136             scanf("%d", ti + i);
137             accti[i] = ti[i] + accti[i - 1];
138         }
139         
140         calc(n, h, fi, di, ti, accti);
141     }
142     
143     return 0;
144 }
View Code