跳至正文

SGU 104 Little Shop of Flowers 解题

  • OI路程

本  质:动态规划 算法描述: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

发表回复

您的电子邮箱地址不会被公开。