pku 1042 Gone Fishing dp

r囧r小猫 2022-07-12 10:54 180阅读 0赞

状态转移为：前i个钓鱼点花费时间j时，所钓鱼的最大值为s\[i\]\[j\]。

\#include <iostream> using namespace std; int s\[26\]\[17\*12\]; int f\[26\], d\[26\], t\[26\], ret\[26\]; int n, h; void findPath(int i, int time) \{ if(i == 0) //此处要看我们dp时,从0开始,还是从1开始. //(从0开始,就是if(i==0)return; //从1开始,就是if(i==1)\{dosomething return;\}) return; int sum = 0; int l = f\[i\]; for(int k = 0; k <= 12\*h; ++k) \{ if(s\[i-1\]\[time-k-t\[i-1\]\]+sum == s\[i\]\[time\]) //回溯找路径的条件. \{ ret\[i\] = k\*5; return findPath(i-1, time-k-t\[i-1\]); \} if(l > 0) \{ sum += l; l -= d\[i\]; \} \} \} int main() \{ while(scanf("%d", &n) && n) \{ scanf("%d", &h); for(int i = 1; i <= n; ++i) scanf("%d", &f\[i\]); for(int i = 1; i <= n; ++i) scanf("%d", &d\[i\]); for(int i = 1; i <= n-1; ++i) scanf("%d", &t\[i\]); memset(s, -1, sizeof(s)); s\[0\]\[0\] = 0; //从0开始初始化 for(int i = 0; i <= n-1; ++i) for(int j = 0; j <= 12\*h; ++j) \{ if(s\[i\]\[j\] != -1) \{ int sum = 0; int l = f\[i+1\]; //由i推i+1的情况时,需要知道的i+1的情况.(Error: f\[i\]) for(int k = 0; k <= 12\*h; ++k) \{ if(j+k+t\[i\] <= 12\*h) s\[i+1\]\[j+k+t\[i\]\] = max(s\[i+1\]\[j+k+t\[i\]\], s\[i\]\[j\]+sum); else break; if(l > 0) \{ sum += l; l -= d\[i+1\]; //由i推i+1的情况时,需要知道的i+1的情况.(Error: d\[i\]) \} \} \} \} int max = -2; int index = 1; for(int i = 1; i <= n; ++i) if(max < s\[i\]\[12\*h\]) \{ max = s\[i\]\[12\*h\]; index = i; \} memset(ret, 0, sizeof(ret)); //初始化,很重要!! findPath(index, 12\*h); for(int i = 1; i <= n-1; ++i) printf("%d, ", ret\[i\]); printf("%d/n", ret\[n\]); printf("Number of fish expected: %d/n/n", s\[index\]\[12\*h\]); \} return 0; \}