2019年電子科技大學ACM暑期前集訓動態規劃專題解題報告

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

這題是一個遍歷所有節點的最小總距離問題。首先把每兩個節點之間的距離存入一個矩陣(雖然好像並不能節省多少時間)。由於是無向圖距離,可以用下三角矩陣。求解方法是狀壓dp,狀態定義爲當前位置和到過的點。可以用一個數(二進制)表示到過的點,多次循環,對於每一個狀態,找到所有可以從其他狀態一步進入該狀態的路徑(也就是枚舉任意兩個不同的到達過的點),選出其中總權最小的一條路徑。根據二進制大小的特點,直接從1(只到過1號位置)枚舉到$(1«n)-1$(到過所有n個位置)即可保證求值的順序正確。枚舉循環結束之後,在到過所有點的狀態中找出最小總權,即爲所求答案

代碼及註釋:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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;
}

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])$,根據該式循環遞推可得出結果

代碼及註釋:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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];
}

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

這題是我瞎jb寫WA得最多的一題。首先這題可以分爲兩個子問題,即取出最多 $n$ 個元素的最佳方案問題;以及把它們插入合適的位置的最佳方案問題。第二個是簡單的貪心問題,都插到相同高度的元素旁邊,如果找不到,就使混亂度+1,插入到首尾或者兩個不同元素間均可,最後增加的混亂度等於在第一個子問題中被全部取出的元素種數。而第一個子問題則是一個複雜的揹包問題,狀態可以定義爲:當前處理到的位置 $i$,前i箇中留下的個數 $v$,上一個的高度 $lst$,留下的字母中存在的高度集 $status$(二進制),共四維。總數據範圍不算大,可以刷一遍所有狀態求解,時間複雜度$O(n^2)$(常數有$8\times2^8$)。而問題的關鍵就在於狀態的轉移,要根據狀態進行較爲複雜的分類處理。詳見以下註釋:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#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;
  }
}

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$,最後遍歷找最大值即可。

代碼及註釋:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#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);
}

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數組的最後一行取最小值,即可得出答案。

代碼及註釋:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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;
  }
}

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

這也是一道狀壓dp的題目。二進制數存儲當前到達過的點,然後循環刷表,刷過去就完事兒了,也沒有必要全部預處理,在循環內部遍歷一下到過的點,得到可以到的點,然後枚舉更新值即可,$O(2^n nT)$時間也完全足夠。刷表完之後,$dp[(i«n)-1]$的值即爲答案。另外,本題可用的小知識點:bitset用於二進制輸入

代碼及註釋:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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;
  }
}

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]$ 有關,所以採用滾動數組優化,節省空間

代碼及註釋:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#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;
}

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

這是一道樹形D(深)P(搜)的題目,首先是有向圖建樹,這個只要根據輸入把節點用一個鄰接鏈表連起來就能用,再順便維護一下入度(是否爲零即可),找到根節點。然後就是寫一個深搜,在遞歸調用返回值中選擇最值來轉移狀態,由於兩人策略不同(重載運算符後,一人要最大值,另一人要最小值),可以用一個bool變量作爲參數記錄當前輪到誰,每次調用時更換該參數即可。最終返回到main()函數的值即爲結果。雖然深搜但實際上時間複雜度也就 $O(n)$

代碼及註釋:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#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;
}

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)$內得到總的最優解。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#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;
}

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次冪最後一行的第一個數。做這題的時候寫了一下矩陣的操作,暫時只寫了需要的乘法操作,並且沒有優化,準備以後有空再把它完善一下作爲模板。

代碼及註釋:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#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];
}

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的題。

代碼及註釋:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#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];
}