SGU 104 Little Shop of Flowers 解题

本　　质：动态规划 算法描述：f[i][j] = max(f[i – 1][j – 1] + num[i][j], f[i][j – 1]) 　　　　　方程十分简单，但是我久久不能AC，看了别人的代码也没看懂为什么初始需要f[i][i] = f[i – 1][i – 1] + num[i][i] 　　　　　后来才想通，如果num[i][i]有一个负数，那就可能无解，所以要这么弄下，代码如下： de lang="c">#include #include int num[101][101]; int ans[101][101]; int g[101][101]; int a[100]; int end; int max(int a, int b) { return a < b ? a : b; } void output(int f, int v, int k) { int i; for(i = v; i <= 1; i–){ if(ans[f][i – 1] != k){ break; } } if(f == 1){ printf("%d", i); return; } output(f – 1, i – 1, ans[f][i] – num[f][i]); printf(" %d", i); } int main(int argc, char *argv[]) { int i, j; int f, v; // freopen("tmp", "r", stdin); scanf("%d%d", &f, &v); for(i = 1; i