刷刷水题压压惊
低级版的能量项链
相当于复习一次中链式dp
这种合并了之后又后效性的题目
都可以用类似的方法做
#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;typedef long long ll;
const int MAXN = 512;
ll x[MAXN], y[MAXN], f[MAXN][MAXN];
int n;int main()
{scanf("%d", &n);REP(i, 0, n) scanf("%lld%lld", &x[i], &y[i]);memset(f, 0x3f, sizeof(f));REP(i, 0, n) f[i][i] = 0;REP(d, 2, n + 1)for(int st = 0; st + d - 1 < n; st++){int i = st, j = st + d - 1;REP(k, i, j)f[i][j] = min(f[i][j], f[i][k] + f[k+1][j] + x[i] * y[k] * y[j]);}printf("%lld\n", f[0][n - 1]);return 0;
}