A

https://acm.uestc.edu.cn/problem/oyhuan-you-shi-jie

这题是一个遍历所有节点的最小总距离问题。首先把每两个节点之间的距离存入一个矩阵(虽然好像并不能节省多少时间)。由于是无向图距离,可以用下三角矩阵。求解方法是状压dp,状态定义为当前位置和到过的点。可以用一个数(二进制)表示到过的点,多次循环,对于每一个状态,找到所有可以从其他状态一步进入该状态的路径(也就是枚举任意两个不同的到达过的点),选出其中总权最小的一条路径。根据二进制大小的特点,直接从1(只到过1号位置)枚举到$(1«n)-1$(到过所有n个位置)即可保证求值的顺序正确。枚举循环结束之后,在到过所有点的状态中找出最小总权,即为所求答案

代码及注释:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, maps[17][2];
ll dp[17][1 << 17];
ll path[17 * 18 / 2];
inline int tri(int m, int n) {//计算三角矩阵下标
  if (m < n) swap(m, n);
  return m * (m + 1) / 2 + n;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int s;
  cin >> n >> s;
  for (int i = 0; i < n; ++i) cin >> maps[i][0] >> maps[i][1];
  swap(maps[0][0], maps[s - 1][0]);
  swap(maps[0][1], maps[s - 1][1]);//把起点交换到开头位置
  for (int i = 0; i < n; ++i)
    for (int j = i + 1; j < n; ++j)
      path[tri(i, j)] =
          abs((ll)maps[i][0] - maps[j][0]) + abs((ll)maps[i][1] - maps[j][1]);//没卵用的预处理
  int end = (1 << n) - 1;
  memset(dp, 0x3f, sizeof(dp));
  dp[0][1] = 0;
  for (int status = 1; status <= end; ++status)//循环,找点,判断修改
    for (int i = 0; i < n; ++i)
      if (status >> i & 1)
        for (int j = i + 1; j < n; ++j)
          if (status >> j & 1)
            dp[j][status] =
                min(dp[j][status], dp[i][status ^ (1 << j)] + path[tri(i, j)]),
            dp[i][status] =
                min(dp[i][status], dp[j][status ^ (1 << i)] + path[tri(i, j)]);
  ll result = LLONG_MAX;
  for (int i = 0; i < n; ++i) result = min(result, dp[i][end]);//在终点路径中找最小
  cout << result;
}

B

https://acm.uestc.edu.cn/problem/wa-kuang-gong-lue

这道题有一个很神奇的特点,要使某个点最终走向西/北边,则其西/北边的点最终都会走向西/北边,因此,如果知道西北角一块矩形范围(从$(0,0)$到$(x,y)$,记作$dp[x][y]$内的最优解,则可以根据这一规律往东或者往南扩展得到$dp[x+1][y]$(假设取红矿)和$dp[x][y+1]$(假设取黑矿),反过来,$dp[x][y]$可以由$dp[x-1][y]$(取红矿)或$dp[x][y-1]$(取黑矿)得到。为取最大值,有$dp[x][y]=max(dp[x-1][y]+red[x][y],dp[x][y-1]+black[x][y])$,根据该式循环递推可得出结果

代码及注释:

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, m;
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  long long red[n][m], black[n][m];
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {//预处理
      cin >> red[i][j];
      if (j) red[i][j] += red[i][j - 1];
    }
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
      cin >> black[i][j];
      if (i) black[i][j] += black[i - 1][j];
    }
  long long dp[n][m];
  memset(dp, 0, sizeof(dp));
  **dp = max(**red, **black);
  for (int i = 1; i < n; ++i)//先算西北边上的
    dp[i][0] = max(dp[i - 1][0] + red[i][0], black[i][0]);
  for (int i = 1; i < m; ++i)
    dp[0][i] = max(red[0][i], dp[0][i - 1] + black[0][i]);
  for (int i = 1; i < n; ++i)//递推求解
    for (int j = 1; j < m; ++j)
      dp[i][j] = max(dp[i - 1][j] + red[i][j], dp[i][j - 1] + black[i][j]);
  cout << dp[n - 1][m - 1];
}

C

https://acm.uestc.edu.cn/problem/shou-ban

这题是我瞎jb写WA得最多的一题。首先这题可以分为两个子问题,即取出最多 $n$ 个元素的最佳方案问题;以及把它们插入合适的位置的最佳方案问题。第二个是简单的贪心问题,都插到相同高度的元素旁边,如果找不到,就使混乱度+1,插入到首尾或者两个不同元素间均可,最后增加的混乱度等于在第一个子问题中被全部取出的元素种数。而第一个子问题则是一个复杂的背包问题,状态可以定义为:当前处理到的位置 $i$,前i个中留下的个数 $v$,上一个的高度 $lst$,留下的字母中存在的高度集 $status$(二进制),共四维。总数据范围不算大,可以刷一遍所有状态求解,时间复杂度$O(n^2)$(常数有$8\times2^8$)。而问题的关键就在于状态的转移,要根据状态进行较为复杂的分类处理。详见以下注释:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int h[100];
ll dp[2][100][8][1 << 8];
bool arrivable[2][100][8][1 << 8];
int all = 0;
inline int c(int x) {//求被全部取出的元素种数,解决第二个子问题
  x = all - x;
  int ans = 0;
  while (x) {
    ans += x & 1;
    x >>= 1;
  }
  return ans;
}
int main() {
  int n, k;
  ios::sync_with_stdio(0);
  cin.tie(0);
  int Case = 0;
  while (cin >> n >> k && n + k) {
    memset(dp, 0x3f, sizeof(dp));
    /*for (int lst = 0; lst < 8; ++lst) {
      dp[1][0][lst][0] = 0;
      dp[0][0][lst][0] = 0;
    }*///后面写好后这段初始化已经不必要了
    all = 0;
    for (int i = 0; i < n; ++i) {
      int tmp;
      cin >> tmp;
      h[i] = tmp - 114514;
      all |= 1 << h[i];
    }//记录总元素集合(二进制)
    if (n - k <= c(0)) {//特判,不写也不会错,不过写了应该可以提速
      cout << "Case " << ++Case << ": " << c(0) << endl << endl;
      continue;
    }
    for (int i = 0; i < n; ++i) {
      if (i + 1 - k <= 1) {
        for (int lst = 0; lst < 8; ++lst)
          dp[i % 2][1][lst][1 << lst] = dp[!(i % 2)][1][lst][1 << lst];
        dp[i % 2][1][h[i]][1 << h[i]] = 1;//这里单独处理v=1的情况,不需要初始化v=0的情况
      }
      for (int v = max(i + 1 - k, 2); v <= i + 1; ++v)//由于最少要留下n-k个,循环下界为i + 1 - k,即在后面全选的情况下可以至少选到n-k个
        for (int status = 1; status < (1 << 8); ++status)
          if ((status | all) == all) {//不可达的状态直接跳过,执行下方else语句,赋值LLONG_MAX >> 2,防止出现后面加数后变负数的情况
            dp[i % 2][v][h[i]][status] = LLONG_MAX >> 2;
            for (int lst = 0; lst < 8; ++lst)
              if (status >> lst & 1) {//与上一个元素相等,则无论是否保留该元素,状态和混乱度都不变,在两者中选较小值
                if (h[i] == lst)
                  dp[i % 2][v][h[i]][status] =
                      min(dp[i % 2][v][h[i]][status],
                          min(dp[!(i % 2)][v - 1][lst][status],
                              dp[!(i % 2)][v][lst][status]));
                else {
                  dp[i % 2][v][lst][status] = dp[!(i % 2)][v][lst][status];//这些lst只能不保留h[i],混乱度和上一次循环相同
                  if ((status >> h[i]) & 1)//考虑从不同状态加入h[i]后进入该状态的情况,选择最小值并加上1
                    dp[i % 2][v][h[i]][status] = min(
                        dp[i % 2][v][h[i]][status],
                        min(dp[!(i % 2)][v - 1][lst][status],
                            dp[!(i % 2)][v - 1][lst][status ^ (1 << h[i])]) +
                            1);
                }
              } else
                dp[i % 2][v][lst][status] = LLONG_MAX >> 2;
          }
    }
    ll Min = LLONG_MAX;//从所有可达的,满足题目限制的点中找到最优解
    for (int v = n - k; v <= n; ++v)
      for (int lst = 0; lst < 8; ++lst)
        for (int status = 0; status < (1 << 8); ++status)
          if ((status | all) == all)
            Min = min(Min, dp[!(n % 2)][v][lst][status] + c(status));
    cout << "Case " << ++Case << ": " << Min << endl << endl;
  }
}

D

https://acm.uestc.edu.cn/problem/xu-lie

K题中的数列是两个方向上升子序列的叠加。对于上升子序列,我们可以维护一个单调递增的数组$dp[]$,用$dp[i]$表示已有的值最小的长度为 $i+1$的子序列末尾值,这样$dp$数组也是单调上升的,对于后面新增的每一个数$num[i]$,$dp[]$中比它小的数和它组成了以$num[i]$结尾的最长上升子序列,用$num[i]$替换第一个比它大的数,不断维护这个数组即可。我们用这个方法,从所有两个方向,对每个数求以其结尾的最长上升子序列$dpl[i]$和$dpr[i]$,以每个数为中心的最长oy序列长度$=min(dpl[i],dpr[i])*2-1$,最后遍历找最大值即可。

代码及注释:

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  scanf("%d", &n);
  int num[n], dpl[n], dpr[n];
  for (int i = 0; i < n; ++i) {
    scanf("%d", num + i);
    dpl[i] = dpr[i] = INT_MAX;
  }
  int rpos = 0, lpos = 0;
  *dpl = *num, *dpr = num[n - 1];
  int llen[n], rlen[n];//加入两端值
  *llen = 1, rlen[n - 1] = 1;
  for (int i = 1; i < n; ++i) {
    int ir = n - 1 - i;//从右端遍历
    if (num[i] > dpl[lpos]) {//处理左端
      dpl[++lpos] = num[i];
      llen[i] = lpos + 1;
    } else {
      int p = lower_bound(dpl, dpl + lpos + 1, num[i]) - dpl;
      dpl[p] = num[i];
      llen[i] = p + 1;
    }
    if (num[ir] > dpr[rpos]) {//处理右端
      dpr[++rpos] = num[ir];
      rlen[ir] = rpos + 1;
    } else {
      int p = lower_bound(dpr, dpr + rpos + 1, num[ir]) - dpr;
      dpr[p] = num[ir];
      rlen[ir] = p + 1;
    }
  }
  int result = 1;
  for (int i = 0; i < n; ++i)
    result = max(result, min(llen[i], rlen[i]) * 2 - 1);//遍历节点找出最大结果
  printf("%d", result);
}

E

https://acm.uestc.edu.cn/problem/shen

该题可以先用一组集合$A[]$处理每组含有的字母有哪些,然后该题把状态定义为当前处理到第i段,以及最后一个字母j,通常情况下有$dp[i][j]=min(dp[i-1][x]+A[i].size()), x\in A[i-1]$.然后本题的重点是特判,通过观察和假设不难得出,如果$A[i]$中含有$x$并且满足:$j \neq x$或$A[i].size()=1$则该值减一(先减再取最值),然后在dp数组的最后一行取最小值,即可得出答案。

代码及注释:

#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int k;
    string s;
    cin >> k >> s;
    set<int> a[s.length() / k];
    int dp[s.length() / k][26];
    memset(dp, 0x7f, sizeof(dp));
    for (int i = 0; i < s.length(); ++i) a[i / k].insert(s[i] - 'a');//将字母处理为 0~25 ,避免浪费空间
    for (int p : a[0]) dp[0][p] = a[0].size();//第1组不存在特判
    for (int i = 1; i < s.length() / k; ++i) {//循环,特判,转移
      for (auto p : a[i]) {
        for (auto q : a[i - 1]) {
          int ans = dp[i - 1][q] + a[i].size();
          if (a[i].find(q) != a[i].end() && (a[i].size() == 1 || p != q)) --ans;
          dp[i][p] = min(dp[i][p], ans);
        }
      }
    }
    int Min=INT_MAX;
    for (auto p : dp[s.length() / k - 1]) Min = min(Min, p);//找出最终答案
    cout << Min << endl;
  }
}

F

https://acm.uestc.edu.cn/problem/wei-ming-ou-yi-lang

这也是一道状压dp的题目。二进制数存储当前到达过的点,然后循环刷表,刷过去就完事儿了,也没有必要全部预处理,在循环内部遍历一下到过的点,得到可以到的点,然后枚举更新值即可,$O(2^n nT)$时间也完全足够。刷表完之后,$dp[(i«n)-1]$的值即为答案。另外,本题可用的小知识点:bitset用于二进制输入

代码及注释:

#include <bits/stdc++.h>
using namespace std;
int main() {
  int t;
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> t;
  for (int ca = 1; ca <= t; ++ca) {
    int n;
    cin >> n;
    bitset<16> init, add[n];
    cin >> init;
    for (int i = 0; i < n; ++i) cin >> add[n - 1 - i];//用bitset变量,可以直接cin输入二进制数,然后用其成员函数转换成其他类型
    unsigned long long dp[1 << n];
    memset(dp, 0, sizeof(dp));
    *dp = 1;//初始化,求方案数的题常常为1而不是0,因为只有一个点也能构成一个方案
    for (int i = 0; i < (1 << n); ++i)//开始刷表
      if (dp[i]) {
        unsigned long path = init.to_ulong();
        for (int j = 0; j < n; ++j)
          if (i >> j & 1) path |= add[j].to_ulong();
        for (int j = 0; j < n; ++j)
          if (!(i >> j & 1))
            if (path >> j & 1) dp[i ^ (1 << j)] += dp[i];
      }
    cout << "Case " << ca << ": " << dp[(1 << n) - 1] << endl;
  }
}

G

https://acm.uestc.edu.cn/problem/zi-chuan

这题的状态定义很浅显易懂,即在前 $i$ 个数中,除k的余数为 $j$ ,这样的字串个数记为 $dp[i][j]$。转移方程也很简单,$j$ 乘10,再加上下一个数后求余,把个数加到对应的状态,即 $dp[i][j]$ 的值应加到 $dp[i+1][(j*10+num[i+1])%k]$ 上,再考虑下个数单独做一个字串的情况即可。最终答案为 $\sum_{i=0}^{n-1}dp[i][0]$,因此循环中可以维护一下sum值。而这题 $dp[i]$ 只与 $dp[i-1]$ 有关,所以采用滚动数组优化,节省空间

代码及注释:

#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, k;
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  char num[n + 1];
  cin >> num;
  for (auto &p : num) p -= '0';//方便后面直接做数组下标
  unsigned long long dp[2][k];
  int a[n];
  memset(dp, 0, sizeof(dp));
  unsigned long long sum = 0;
  bool now = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < k; ++j) dp[now][(j * 10 + num[i]) % k] += dp[!now][j];//把每一个量向后转移
    ++dp[now][num[i] % k];//num[i]单独成字串
    memset(dp[!now], 0, sizeof(dp[!now]));
    sum += dp[now][0];
    now = !now;
  }
  cout << sum;
}

H

https://acm.uestc.edu.cn/problem/vanyou-xi

这是一道树形D(深)P(搜)的题目,首先是有向图建树,这个只要根据输入把节点用一个邻接链表连起来就能用,再顺便维护一下入度(是否为零即可),找到根节点。然后就是写一个深搜,在递归调用返回值中选择最值来转移状态,由于两人策略不同(重载运算符后,一人要最大值,另一人要最小值),可以用一个bool变量作为参数记录当前轮到谁,每次调用时更换该参数即可。最终返回到main()函数的值即为结果。虽然深搜但实际上时间复杂度也就 $O(n)$

代码及注释:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
list<int> a[1000000];
int num[1000000];
bool fa[1000000];
struct sc {//保存两人分数,重载运算符
  ll e, m;
  sc(){};
  sc(ll e, ll m) {
    this->e = e;
    this->m = m;
  }
  friend bool operator<(sc a, sc b) {
    return a.e == b.e ? a.m > b.m : a.e < b.e;
  }
};
sc dp(int pos, bool moe) {
  sc ans(0, 0);
  bool init = 1;
  if (moe) {
    for (auto &p : a[pos]) {//第一次赋值,之后比较再更新
      if (init) {
        ans = dp(p, !moe);
        init = 0;
        continue;
      }
      ans = max(ans, dp(p, !moe));
    }
    a[pos].clear();//强迫症清内存。。。
    return sc(ans.e, ans.m + num[pos]);
  }
  for (auto &p : a[pos]) {//思路与上面类似
    if (init) {
      ans = dp(p, !moe);
      init = 0;
      continue;
    }
    ans = min(ans, dp(p, !moe));
  }
  a[pos].clear();
  return sc(ans.e + num[pos], ans.m);
}
int main() {
  char start[4];
  int n;
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> start >> n;
  bool moe = *start == 'm';
  for (int i = 0; i < n; ++i) cin >> num[i];
  for (int i = 0; i < n - 1; ++i) {//建立邻接链表
    int x, y;
    cin >> x >> y;
    a[x - 1].push_back(y - 1);
    fa[y - 1] = 1;//记下该点入度不为0
  }
  int root;
  for (int i = 0; i < n; ++i)
    if (!fa[i]) {//找根节点
      root = i;
      break;
    }
  sc result = dp(root, moe);
  cout << result.e << ' ' << result.m;
}

I

https://acm.uestc.edu.cn/problem/gong-lue-mei-zhi

这道题首先看起来很复杂,但实际就是一个背包问题。每个元素的属性可以简化成价值a,花费c,和达到先决条件所需花费d,其中在d上面的花费是公共的,这样就是两个子问题:分配先决条件d花费的最优解;以及在问题一的条件下,用剩余的钱获得最大价值的最优解。第一个子问题可以直接枚举,把元素按d排序,则第二个子问题是前几个元素的01背包问题,两个问题都很好解决。然而直接在循环枚举中写01背包时间复杂度高达$O(m n^2)$,结果当然是TLE。再分析问题,会发现存在很多被重复计算的值。所以只需跑一次01背包,在过程中导出问题一的各种情况下的最优解,即可在$O(mn)$内得到总的最优解。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
struct M {
  int a;
  ll c, d;
  M() {}
  M(int a, ll c, ll d) {
    this->a = a;
    this->c = c;
    this->d = d;
  }
  bool operator<(M x) { return this->d < x.d; }//重载,按d排序
} target[5000];
int m;
int main() {
  int n, k, x, y;
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k >> x >> y;
  for (int i = 0; i < n; ++i) {
    int tmp;
    cin >> target[i].a >> tmp >> target[i].c >> target[i].d;
    target[i].c = max((target[i].c - tmp) * y, 0LL);
    target[i].d = max((target[i].d - k) * x, 0LL);
  }//输入并简化各值
  sort(target, target + n);
  ll dp[m + 1];
  memset(dp, 0, sizeof(dp));
  ll Max = 0;
  for (int i = 0; i < n; ++i) {//开始跑0-1背包
    if (m < target[i].d) break;
    for (int j = m; j >= target[i].c; --j)//倒序可以直接一维数组
      dp[j] = max(dp[j], dp[j - target[i].c] + target[i].a);
    Max = max(Max, dp[m - target[i].d]);//导出子问题最优解,与全局最优解比较更新
  }
  cout << Max;
}

K

https://acm.uestc.edu.cn/problem/chou-qia

首先,从数据范围可以看出,要求复杂度$O(logn)$进行递推,这很容易想到矩阵快速幂。这道题的难点就在这个矩阵上面。我之前想了很久,但是思维局限在二维或三维矩阵上,一直没有推出一个常矩阵。事实上这是一个m+1阶方阵,用一个列向量表示第i次碎片数量从0到m的概率。记作$dp[i]=(dp[i][0],dp[i][0]…dp[i][m])^\top$,然后就可以很容易的递推写出整个矩阵。其中可以把直接抽中定义为直接进入$dp[i+1][m]$状态,即在第最后一行各元素全部加上直接抽中的概率。这样得到的矩阵求快速幂,然后乘初始状态。由于初始状态(一次也没抽)的$dp[0]=(1,0,0,0…)^\top$,最后的结果即为矩阵n次幂最后一行的第一个数。做这题的时候写了一下矩阵的操作,暂时只写了需要的乘法操作,并且没有优化,准备以后有空再把它完善一下作为模板。

代码及注释:

#include <bits/stdc++.h>
const long long M = 1000000007;
using namespace std;
struct martix_int {
  int w, h;
  long long **data;
  martix_int(int w, int h) {//这里的构造方式,既能data[i][j]访问,也能 memset(*data, 0, sizeof(long long) * h * w); 置零。
    this->w = w;
    this->h = h;
    data = new long long *[h];
    *data = new long long[h * w];
    for (int i = 1; i < h; ++i) data[i] = data[i - 1] + w;
    memset(*data, 0, sizeof(long long) * h * w);
  }
};
martix_int operator*(martix_int x, martix_int y) {//无优化的三层循环
  martix_int result = martix_int(x.h, y.w);
  for (int i = 0; i < x.h; ++i)
    for (int j = 0; j < x.w; ++j)
      for (int k = 0; k < y.w; ++k)
        result.data[i][k] =
            (result.data[i][k] + x.data[i][j] * y.data[j][k]) % M;
  return result;
}
martix_int Pow(martix_int x, int n) {//简单的递归快速幂
  martix_int ans(x.h, x.w);
  if (!n)
    for (int i = 0; i < x.w; ++i) ans.data[i][i] = 1;
  else if (n == 1)
    ans = x;
  else {
    martix_int tmp = Pow(x, n / 2);
    ans = tmp * tmp;
    if (n % 2) ans = ans * x;
  }
  return ans;
}
int main() {
  int n, m;
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  double tmp1, tmp2;
  cin >> tmp1 >> tmp2;
  long long p1 = round(tmp1 * 1000), p = round(tmp2 * 1000);//然而对于之前存在精度误差问题的数据,round()并没有卵用
  martix_int P(m + 1, m + 1);
  for (int i = 0; i <= m; ++i) P.data[i][i] = 1000 - (m - i) * p - p1;
  for (int i = 0; i <= m - 1; ++i) P.data[i + 1][i] = (m - i) * p;
  for (int i = 0; i <= m; ++i) P.data[m][i] += p1;
  P = Pow(P, n);
  cout << P.data[m][0];
}

L

https://acm.uestc.edu.cn/problem/zhde-jiang-bei

这道题是一个比较标准的斜率优化dp,首先看到静态的区间和,先把前缀和弄出来。 状态转移方程很简单,$dp[i]=min{dp[j]+(a-L)^2},j<i,a=sum[i]-sum[j]+i-j-1$ 但是直接遍历,$O(n^2)$的时间复杂度显然会TLE,所以需要一个快速找出$min{dp[j]+(a-L)^2}$的算法。我们把整个式子拆开,可以定义

$h(x)=sum[x]+x$

$g(x)=dp[x]+h^2(x)+2xL$

则点$(h(x),g(x))$可表示第x个元素在该题中判断优先级的一个依据。对于每一个i,找到第一个左斜率小于$k[i]=2h(i)$,右斜率大于$k[i]$的点,即为取得$min{dp[j]+(a-L)^2}$的点,即可算出$dp[i]$。最后的$dp[n-1]$即为所求。在这个过程中,左斜率大于右斜率的点显然不可能被取,可以直接去掉,又因为 $k[i]$ 和 $i$ 成正相关,所以 $i$ 从小到大循环时,右斜率小于 $k[i]$ 的点也可以直接删掉,后面不会再取到。这样就成了一个单调队列(和数据结构专题的问题D类似)。后来看了模板通常都喜欢用数组模拟双端队列,我这次写的deque(时间开销较大),不知道这类会不会有卡STL的题。

代码及注释:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, l;
ll sum[10000000], dp[10000000];
inline ll Pow(ll a) { return a * a; }
inline ll h(int i) { return sum[i] + i; }
inline ll g(int x) { return dp[x] + Pow(h(x)) + 2 * h(x) * l + 2 * h(x); }
inline bool compare1(int p, int q, int r) {
  return (g(p) - g(q)) * (h(q) - h(r)) < (h(p) - h(q)) * (g(q) - g(r));
}
inline bool compare2(int p, int q, int i) {
  return (g(q) - g(p)) < 2 * h(i) * (h(q) - h(p));
}//定义各个函数,简化后面操作。
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> l;
  cin >> *sum;
  for (int i = 1; i < n; ++i) {//前缀和
    cin >> sum[i];
    sum[i] += sum[i - 1];
  }
  deque<int> rest;
  rest.push_front(0);
  dp[0] = Pow(h(0) - l);//第一组单独处理
  // for(int &p:rest)cout<<p<<endl;
  for (int i = 1; i < n; ++i) {
    while (rest.size() >= 2 &&
           compare2(rest[rest.size() - 1], rest[rest.size() - 2], i))//加判断防止越界
      // K(rest[rest.size() - 1], rest[rest.size() - 2]) < k(i))
      rest.pop_back();
    dp[i] = min(Pow(h(i) - l),
                dp[rest.back()] + Pow(h(i) - h(rest.back()) - 1 - l));//更新值
    while (
        rest.size() >= 2 &&
        compare1(i, rest[0], rest[1]))  // K(i, rest[0]) < K(rest[0], rest[1]))
      rest.pop_front();//加入新的点
    rest.push_front(i);
  }
  cout << dp[n - 1];
}