首页 > 代码库 > [luoguP1388] 算式（DP）
[luoguP1388] 算式（DP）
传送门
看这个n<=15本以为是个状压DP
还是too young
这个题最神奇的地方是加括号是根据贪心的策略。
发现只有在一连串的加号两边加上括号才是最优的（想一想，为什么？）
f[i][j]表示前i个数加j个乘号的最优解
#include <cstdio>#define max(x, y) ((x) > (y) ? (x) : (y))int n, m;int f[20][20];int main(){ int i, j, k, x; scanf("%d %d", &n, &m); for(i = 1; i <= n; i++) { scanf("%d", &x); f[i][0] = f[i - 1][0] + x; } for(i = 2; i <= n; i++) for(j = 1; j < i; j++) for(k = 1; k < i; k++) f[i][j] = max(f[i][j], f[k][j - 1] * (f[i][0] - f[k][0])); printf("%d\n", f[n][m]); return 0;}
[luoguP1388] 算式（DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。