dp学习笔记 5 序列删除(区间dp)

题目 题意: 给定n个数，把除a1和an的其余数全部删除。删除第i个数的代价为a[i]*a[l]*a[r]. a[l]和a[r]是a[i]左右尚未被删除的数。 思路: 区间dp，一直在想先删除哪边另一边就会变，绕不明白。只能说对区间dp的理解不是很到位。 对于区间[i,j]枚举中间点k，k即区间[i,j]中最后删除的数，他的代价自然容易计算。 f[i][j] = min(f[i][j],f[i][k-1]+f[k+1][j]+a[k]a[i-1]a[j+1]) ！这里要注意，直接把数组赋值为INF会寄，因为在转移式中存在非法区间，非法区间代价是0，但是却记为INF。可以特判边界，因为只会在k=i或者k=j时存在非法边界，也可以把所有非法区间赋值为0。 时间复杂度: O(nnn) 代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i>n;
   for(int i=1;i>a[i];
   for(int i=2;i