poj-1042

#include <stdio.h>  #include <malloc.h>  struct fishingOP {      int maxFishing;      int stayInterval;  };  typedef struct fishingOP fishingOP;  void getMostFish(int * fi, int * di, int * ti, int lakeNum, int intervalNum) {      fishingOP ** matrix = (fishingOP **)malloc(sizeof(fishingOP *) * lakeNum);      for (int i = 0; i < lakeNum; i++) {          *(matrix + i) = (fishingOP *)malloc(sizeof(fishingOP) * (intervalNum + 1));      }      for (int i = 0; i < lakeNum; i++) {          for (int j = 0; j < intervalNum + 1; j++) {              matrix[i][j].maxFishing = -1;          }      }      for (int i = lakeNum-1; i >= 0; i--) {          for (int j = 0; j < intervalNum + 1; j++) {              if (j == 0) { // no time to fishing                  // printf("%d %d 0\n", i, j);                  matrix[i][j].maxFishing = 0;                  matrix[i][j].stayInterval = 0;                  continue;                  } else if (i == lakeNum-1 && j == 1) { // can only fishing from the last lake, and only 1 interval                  matrix[i][j].maxFishing = fi[i];                  // printf("%d %d %d\n", i, j, matrix[i][j].maxFishing);                  matrix[i][j].stayInterval = 1;                  continue;              } else if (i == lakeNum-1 && j >= 1) { // can only fishing from the last lake, stay more than 1 interval                  if (fi[i] - di[i] *(j - 1) > 0) {                      matrix[i][j].maxFishing = matrix[i][j-1].maxFishing + fi[i] - di[i] *(j-1);                  } else {                      matrix[i][j].maxFishing = matrix[i][j-1].maxFishing; // if have stay, but no fish, of course equals previuos interval                  }                  matrix[i][j].stayInterval = j;                  // printf("%d %d %d\n", i, j, matrix[i][j].maxFishing);                  continue;              } else {                  int stayInterval = 0;                  if (j - ti[i] < 0) { // no time to next lake                      int fishNumCurLakeAcc = 0;                      int fishIntervalNum = fi[i];                      for (int k = 1; k <= j; k++) { // iterate all possible stay interval num                          fishNumCurLakeAcc += fishIntervalNum;                          fishIntervalNum -= di[i];                          if (fishIntervalNum < 0) {                              fishIntervalNum = 0;                          }                      }                      matrix[i][j].maxFishing = fishNumCurLakeAcc;                      stayInterval = j;                      matrix[i][j].stayInterval = stayInterval;                                        } else { // still have time to go next lake, so can fish some time here.                      int maxfishingNum = matrix[i+1][j - ti[i]].maxFishing; // no fishing in lake i.                      int fishNumCurLakeAcc = 0;                      int fishIntervalNum = fi[i];                                            for (int k = 1; k <= j; k++) { // iterate all possible stay interval num                          fishNumCurLakeAcc += fishIntervalNum;                          int curFishNum;                          if (j - k - ti[i] >= 0) {                              curFishNum = fishNumCurLakeAcc + matrix[i+1][j - k - ti[i]].maxFishing;                          } else {                              curFishNum = fishNumCurLakeAcc;                          }                          fishIntervalNum -= di[i];                          if (fishIntervalNum < 0) {                              fishIntervalNum = 0;                          }                          if (curFishNum >= maxfishingNum) {                              maxfishingNum = curFishNum;                              stayInterval = k;                          }                      }                      matrix[i][j].maxFishing = maxfishingNum;                      matrix[i][j].stayInterval = stayInterval;                  }                                    // printf("%d %d %d stay: %d\n", i, j, matrix[i][j].maxFishing, matrix[i][j].stayInterval*5);              }          }      }      int i = 0;      int j = intervalNum;      bool firstTime = 1;      while(1) {          if (i == lakeNum) {              break;          }          if (!firstTime) {              printf(", ");          } else {              firstTime = 0;          }          int stayInterval;          if (j >= 0) {               stayInterval = matrix[i][j].stayInterval;          } else {              stayInterval = 0;          }          printf("%d", stayInterval*5);          j = j - stayInterval - ti[i];          i = i + 1;      }      printf("\n");      printf("Number of fish expected: %d\n\n", matrix[0][intervalNum].maxFishing);      for (int i = 0; i < lakeNum; i++) {          free(*(matrix + i));          *(matrix + i) = NULL;      }      free(matrix);      matrix = NULL;  }  int main() {      while(1) {          int lakeNum = 0;          int hour = 0;          scanf("%d", &lakeNum);          if (lakeNum == 0) {              break;          }          scanf("%d", &hour);          int intervalNum = hour*12;          int * fi = (int *)malloc(sizeof(int) * lakeNum);          int * di = (int *)malloc(sizeof(int) * lakeNum);          for (int i = 0; i < lakeNum; i++) {              scanf("%d", fi+i);          }          for (int i = 0; i < lakeNum; i++) {              scanf("%d", di+i);          }          int * ti = (int *)malloc(sizeof(int) * (lakeNum-1));          for (int i = 0; i < lakeNum-1; i++) {              scanf("%d", ti + i);          }          getMostFish(fi, di, ti, lakeNum, intervalNum);          free(fi);          fi = NULL;          free(di);          di = NULL;          free(ti);          ti = NULL;      } }

DP， 变种背包， 只是每件物品都有多个背包， 还要注意lake全部钓鱼后，继续掉下去就不能再减di了。

二维数组用在上面

matix【i】【j】 代表从第一个lake开始， 总共有j个interval(5分钟) 能钓到的鱼最多。

考虑如下：

<1> j == 0, 没有时间钓鱼， 所以最大鱼数为0

<2> i == lakeNum, 钓鱼从最后一个lake开始， 最大的鱼数是lake从此能钓到的所有鱼。

<3> j 不足以 跑到下一个lake， 然后只能在lake上钓鱼， 最大的鱼数是在j的时间内能钓到的最多的鱼

<4> j也可以跑到下一个lake， 然后就可以再分了， 在这里lake停留一段时间(1 ~ j），

比较每个停留时间能钓到的最大鱼数。(多种选择， 与0-1背包不同， 0-1背包里只有一件物品。

这里也有两种情况需要注意：

（1） 停留了K， 剩下的时间还能跑到下一个lake， 那么鱼数 就是 在这段k段时间里钓到的鱼 加上 matix[i+1][j -k - 下一个lake花的时间]

(2)停留K， 但剩下的时间还不够下一个lake， 那么最大的鱼数就是这段时间在第一个lake能钓到的鱼.

事实上，三维数组更方便

matix[i][j][k] 代表 从第一个lake开始， 总共由 j interval， 并且在 第一个lake 钓 k 最大鱼数在一段时间内.

这个题目也可以用贪心法， 以后补上.

为便于跟踪轨迹， 除记录每种情况的最大鱼数外， 还记录了停留时间.

实际编写DP时， 步骤之间很难耦合紧密， 考虑的极限情况也很多.