[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() 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; }

　　

上一篇：[luoguP1773] 符文之语_NOI导刊2010提高（02）（DP）

下一篇：[luoguP2622] 关灯问题II（状压最短路）

---

DP