总的来说，感觉这次比较简单，应该是疫情上网课的原因，算的数据也比较小，虽然最后延长了15分钟，但好好复习应该都可以做完

综合题 40

矩阵连乘 10

5x5矩阵，挺好算的，送分

  1. 求m[1][5]
  2. 最少乘法次数
  3. 最优解

流水作业调度变形 10

只是把作业换成切菜和炒菜了，送分

  1. 安排顺序
  2. 时间

最短路径 10

没什么好说的，就是给了个图，求到各点的最短路径，送分

最小生成树 10

6节点 10个边

  1. kruskal求最小生成树 送分

  2. 比较prim算法和krusal哪个更适合

第二问就是比较时间复杂度，一个是O(nm)另一个是O(mlog(m))比大小就行

算法分析

时间复杂度 15

  1. 求时间复杂度
  2. 比较二分、归并、上面算法的上界

也是比较好算，第二问别记错就行 log(n) nlog(n) $n^2$ 送分

01背包变形 15

p=[48 49 40 45]
v=[8 7 10 9]
m=100
  1. 回溯法
  2. 优先级队列分支限界

复习到了的，一般都会 送分

算法设计

称重 15

255个鹅蛋，1个鸭蛋，混一块，给个天平，设计算法称出鸭蛋

  1. 实际不高于log(n)复杂度算法
  2. 100个蛋，最多称多少次，找到鸭蛋
  3. 设计一个更快的算法

和课件称金块的很像，第一问二分放天平两边，第二问6个，第三问三分四分…… 送分

积木堆 15

n堆积木，每次合并2堆，合并(n-1)次，求最小合并代价。代价：合并的两个积木堆积木数量和

  1. 设计算法 送分
  2. 给一组数据，求合并策略 送分
  3. 只能合并挨着的两堆，设计dp算法，求最小代价

一二问贪心，贪心策略：每次合并，最少的两堆优先

第二问，类似哈夫曼树的求解过程

第三问区间dp，就是石子合并

设有N堆沙子排成一排，其编号为1，2，3，…，N（N< =300）。每堆沙子有一定的数量，可以用一个整数来描述，现在要将N堆沙子合并成为一堆，每次只能合并相邻的两堆，合并的代价为这两堆沙子的数量之和，合并后与这两堆沙子相邻的沙子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同，如有4堆沙子分别为1 3 5 2我们可以先合并1、2堆，代价为4，得到4 5 2又合并1，2堆，代价为9，得到9 2，再合并得到11，总代价为4+9+11=24，如果第二步是先合并2，3堆，则代价为7，得到4 7，最后一次合并代价为11，总代价为4+7+11=22；问题是：找出一种合理的方法，使总的代价最小。输出最小代价。

// 状态转移方程
// dp[i][j]表示[i,j]区间合并最小代价
// dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1])


#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int a[N],s[N],dp[N][N];
int main(){
    int n,t;
    cin>>n;
    for(int i=1;i<=n;i++){ // 1开始
        cin>>s[i];
        s[i]+=s[i-1];
    }
    for(int len=2;len<=n;len++){
        for(int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            dp[i][j]=0x3fffffff; //初始化
            for(int k=i;k<=j;k++){
                dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+s[j]-s[i-1]);
            }
        }
    }
    cout<<dp[1][n];
    system("pause");
    return 0;
}