本期笔记的内容为区间DP

不知不觉已经更新到了第五期~

相关链接：

1.往期笔记： 查看
2.来源：yxc老师的算法提高课

【提高版】DP知识笔记5 有猷 编

例题：

1. 能量项链

思路：

2. 凸多边形的划分

思路：
要用高精，比较 烦，给下C++代码： （别走，下面还有题目！）

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
#define re register
#define Re register
#define MAXN 55
struct bignum{
    int lens;
    int arr[550];
}zero;
void prn(bignum a){
    if(a.lens == 0)cout << 0;
    for(re int i = a.lens;i >= 1;i--){
        cout << a.arr[i];
    }
    cout << endl;
}
bool operator<(bignum a,bignum b){
    if(a.lens != b.lens)return a.lens < b.lens;
    for(re int i = a.lens;i >= 1;i--){
        if(a.arr[i] != b.arr[i])return a.arr[i] < b.arr[i];
    }
    return false;
}
bignum operator*(bignum a,bignum b){
    bignum ans = zero;
    for(re int i = 1;i <= a.lens;i++){
        for(re int j = 1;j <= b.lens;j++){
            ans.arr[i + j - 1] += a.arr[i] * b.arr[j];
        }
    }
    for(re int i = 1;i <= a.lens + b.lens + 5;i++){
        ans.arr[i + 1] += ans.arr[i] / 10;
        ans.arr[i] %= 10;
        if(ans.arr[i])ans.lens = i;
    }
    return ans;
}
bignum operator+(bignum a,bignum b){
    bignum ans = zero;
    for(re int i = 1;i <= a.lens + 3 || i <= b.lens + 3;i++){
        ans.arr[i] += a.arr[i] + b.arr[i];
        if(ans.arr[i])ans.lens = i;
        ans.arr[i + 1] += ans.arr[i] / 10;
        ans.arr[i] %= 10;
    }
    return ans;
}
bignum flat(int a){
    bignum ans = zero;
    for(re int i = 1;a;i++){
        ans.arr[i] = a % 10;
        ans.lens = i;
        a /= 10;
    }
    return ans;
}
int n;
bignum val[MAXN],opt[MAXN][MAXN];
int main() {
    cin >> n;
    for(re int i = 1;i <= n;i++){
        int x;
        cin >> x;
        val[i] = flat(x);
    }
    for(re int i = n;i >= 1;i--){
        for(re int j = i + 2;j <= n;j++){
            for(re int k = i + 1;k < j;k++){
                if(opt[i][k] + opt[k][j] + val[i] * val[j] * val[k] < opt[i][j] || k == i + 1)
                    opt[i][j] = opt[i][k] + opt[k][j] + val[i] * val[j] * val[k];
            }
        }
    }
    prn(opt[1][n]);
    return 0;
}

3.棋盘分割