首页 > 代码库 > [luoguP1040] 加分二叉树(DP)
[luoguP1040] 加分二叉树(DP)
传送门
区间DP水题
代码
#include <cstdio>#include <iostream>#define N 41#define max(x, y) ((x) > (y) ? (x) : (y))int n;int a[N], f[N][N], pre[N][N];inline int read(){ int x = 0, f = 1; char ch = getchar(); for(; !isdigit(ch); ch = getchar()) if(ch == ‘-‘) f = -1; for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - ‘0‘; return x * f;}inline void solve(int l, int r){ printf("%d ", pre[l][r]); if(l <= pre[l][r] - 1) solve(l, pre[l][r] - 1); if(pre[l][r] + 1 <= r) solve(pre[l][r] + 1, r);}int main(){ int i, j, k; n = read(); for(i = 1; i <= n; i++) f[i][i] = read(), pre[i][i] = i; for(i = n; i >= 1; i--) for(j = i + 1; j <= n; j++) { if(f[i][i] + f[i + 1][j] > f[i][j]) f[i][j] = f[i][i] + f[i + 1][j], pre[i][j] = i; for(k = i + 1; k < j; k++) if(f[i][k - 1] * f[k + 1][j] + f[k][k] > f[i][j]) f[i][j] = f[i][k - 1] * f[k + 1][j] + f[k][k], pre[i][j] = k; if(f[j][j] + f[i][j - 1] > f[i][j]) f[i][j] = f[j][j] + f[i][j - 1], pre[i][j] = j; } printf("%d\n", f[1][n]); solve(1, n); return 0;}
[luoguP1040] 加分二叉树(DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。