【算法竞赛入门经典—训练指南】学习笔记（含例题代码与思路）第一章：算法设计基础...

分手后的思念是犯贱 2022-01-09 10:51 974阅读 0赞

学了一年半\\(OI\\)马上都要退役了，结果居然还没怎么碰过蓝书=\_=。这一个月开始刷，力图把上面的重点都尽可能弄懂。

> 例题\\(1\\) 勇者斗恶龙（\\(UVa11292\\)）

*  一眼费用流，再看一眼发现卡不过去。
 *  仔细思考会发现贪心即可。因为骑士能力值和花费是一致的，所以排个序挨个砍，尽可能不把高费骑士浪费在低费头上即可。

#include <bits/stdc++.h> using namespace std; const int N = 20010; int n, m, A[N], B[N]; int main () { while (cin >> n >> m) { if (n == 0 && m == 0) break; for (int i = 1; i <= n; ++i) cin >> A[i]; for (int i = 1; i <= m; ++i) cin >> B[i]; sort (A + 1, A + 1 + n); sort (B + 1, B + 1 + m); int ans = 0; bool failed = false; for (int i = 1, j = 1; i <= n; ++i) { while (B[j] < A[i]) ++j; if (j > m) { failed = true; break; } if (B[j] >= A[i]) ans += B[j++]; } if (failed) puts ("Loowater is doomed!"); else cout << ans << endl; } }

--------------------

> 例题\\(2\\) 突击战（\\(UVa11729\\)）

*  对于这种要考虑很多条件之间组合的，我们先从两个开始思考。
    
     *  建议在纸上自己画一下两个任务的执行先后对终止时间的影响。
 *  思考清楚后贪心即可，执行时间长的先交代。

#include <bits/stdc++.h> using namespace std; const int N = 1010; int n, _case, sumt1[N]; struct Task { int t1, t2; bool operator < (const Task &rhs) const { return t2 > rhs.t2; } }Arr[N]; int main () { while (cin >> n) { if (n == 0) break; for (int i = 1; i <= n; ++i) cin >> Arr[i].t1 >> Arr[i].t2; sort (Arr + 1, Arr + 1 + n); for (int i = 1; i <= n; ++i) sumt1[i] = sumt1[i - 1] + Arr[i].t1; int ans = 0; for (int i = 1; i <= n; ++i) { ans = max (ans, sumt1[i] + Arr[i].t2); } cout << "Case " << ++_case << ": " << ans << endl; } }

--------------------

> 例题\\(3\\) 分金币（\\(UVa11300\\)）

*  环形均分纸牌问题，需要猜一个结论：一定存在两个点之间没有金币交换。我们枚举这个点就可以。
 *  \\(O(N^2)->O(N)\\)的优化：设枚举点为\\(k\\)，把要最小化的答案表示出来，会发现是一个货仓选址的模型，取中位数即可。

#include <bits/stdc++.h> using namespace std; #define int long long const int N = 1000010; int n, A[N], S[N]; signed main () { while (cin >> n) { int tot = 0, ans = 0; for (int i = 1; i <= n; ++i) {cin >> A[i]; tot += A[i];}; // s[i] = \sum{A[i] - Average} for (int i = 1; i <= n; ++i) S[i] = S[i - 1] + (A[i] - tot / n); sort (S + 1, S + 1 + n); for (int i = 1; i <= n; ++i) ans += abs (S[i] - S[n / 2 + 1]); cout << ans << endl; } }

--------------------

> 例题\\(4\\) 墓地雕塑（\\(LA3708\\)）

*  考虑原题是正\\(N\\)边形变成\\(N + M\\)边形。
 *  两个结论：
    
     *  变化前后的两个正多边形一定有一个点重合（不妨设其顺时针距离为\\(0\\)）
     *  其他的点只需要每一个点去寻找一个最近的对应点即可，可以证明不会存在两个点找同一个点的状况。

#include <bits/stdc++.h> using namespace std; const int N = 1010; int n, m; double disp, disn; double dis (int x, int y) { return fabs (disp * x - disn * y); } int main () { while (cin >> n >> m) { double ans = 0; disp = 10000.0 / (n * 1.0); disn = 10000.0 / ((n + m) * 1.0); for (int i = 0, p = 0; i < n; ++i) { //对初始点配位 while (p + 1 < (n + m) && dis (i, p) > dis (i, p + 1)) { p = p + 1; } ans += dis (i, p); p = p + 1; } printf ("%.4lf\n", ans); } }

--------------------

> 例题\\(5\\) 蚂蚁（\\(UVa10881\\)）

*  关键在于要想到蚂蚁的相对位置不变～明白这一点剩下就简单了。
 *  两个蚂蚁的碰撞可以想象为它们穿过彼此继续前进但是灵魂互换，这样我们可以得到坐标和方向正确但是顺序不确定的坐标序列，根据上面的结论确定顺序编号即可。

#include <bits/stdc++.h> using namespace std; const int N = 10010; int T, l, t, n; int pos[N], str[N]; struct Ant { int id, pos; char dir; bool operator < (Ant rhs) const { //相对位置不变 return pos == rhs.pos ? dir < rhs.dir : pos < rhs.pos; } }Ap[N], An[N]; char res[4][10] = {"L", "R", "Turning", "Fell off"}; int main () { cin >> T; for (int Case = 1; Case <= T; ++Case) { cin >> l >> t >> n; for (int i = 1; i <= n; ++i) { cin >> Ap[i].pos >> Ap[i].dir; Ap[i].id = i; An[i].dir = Ap[i].dir; An[i].pos = Ap[i].dir == 'R' ? Ap[i].pos + t : Ap[i].pos - t; } sort (Ap + 1, Ap + 1 + n); sort (An + 1, An + 1 + n); for (int i = 1; i <= n; ++i) { // printf ("id = %d, pos = %d, dir = %c\n", Ap[i].id, An[i].pos, An[i].dir); pos[Ap[i].id] = An[i].pos; if (An[i].dir == 'L') str[Ap[i].id] = 0; if (An[i].dir == 'R') str[Ap[i].id] = 1; // printf ("pos_now = %d, pos_pre = %d\n", An[i].pos, An[i - 1].pos); if (i + 1 <= n && An[i].pos == An[i + 1].pos) str[Ap[i].id] = 2; if (0 <= i - 1 && An[i].pos == An[i - 1].pos) str[Ap[i].id] = 2; if (l < An[i].pos || An[i].pos < 0) str[Ap[i].id] = 3; } printf ("Case #%d:\n", Case); for (int i = 1; i <= n; ++i) { if (str[i] == 3) puts (res[3]); else { printf ("%d %s\n", pos[i], res[str[i]]); } } printf ("\n"); } }

--------------------

> 例题\\(6\\) 立方体成像（\\(LA2995\\)）

*  每一个小块如果颜色无法对应就删删删～
 *  关键在于确定立方体的每一个块的每一个面应该怎么表示。用函数式编程的思想来简化代码。

#include <bits/stdc++.h> using namespace std; const int N = 15; #define rep(i,n) for (int i = 0; i < (n); ++i) int n; char pos[N][N][N], view[6][N][N]; void get (int k, int i, int j, int len, int &x, int &y, int &z) { if (k == 0) x = len, y = j, z = i; if (k == 1) x = n - j - 1, y = len, z = i; if (k == 2) x = n - len - 1, y = n - j - 1, z = i; if (k == 3) x = j, y = n - len - 1, z = i; if (k == 4) x = n - i - 1, y = j, z = len; if (k == 5) x = i, y = j, z = n - len - 1; } int main () { while (cin >> n) { if (n == 0) break; rep (i, n) rep (k, 6) rep (j, n) scanf (" %c", &view[k][i][j]); rep (i, n) rep (j, n) rep (k, n) pos[i][j][k] = '#'; rep (k, 6) rep (i, n) rep (j, n) if (view[k][i][j] == '.') { rep (p, n) { int x, y, z; get (k, i, j, p, x, y, z); pos[x][y][z] = '.'; // 清除视图k下坐标 (i, j) 所有深度的立方体 } } while (true) { // 不能再修改为止 bool done = true; rep (k, 6) rep (i, n) rep (j, n) if (view[k][i][j] != '.') { rep (p, n) { int x, y, z; get (k, i, j, p, x, y, z); if (pos[x][y][z] == '.') continue; // 空 if (pos[x][y][z] == '#') { // 暴露在外且未填 pos[x][y][z] = view[k][i][j]; break; } if (pos[x][y][z] == view[k][i][j]) break; // 暴露在外且颜色并不矛盾 pos[x][y][z] = '.'; // 暴露在外且颜色矛盾 -> 删除并让下一个深度暴露在外 done = false; } } if (done) break; } int ans = 0; rep (i, n) rep (j, n) rep (k, n) { if (pos[i][j][k] != '.') ans++; } printf ("Maximum weight: %d gram(s)\n", ans); } }

--------------------

> 例题\\(7\\) 偶数矩阵（\\(UVa11464\\)）

*  常见套路：固定第一行以后，后面的行都可以直接\\(O(N)\\)递推，复杂度\\(O(2^N\*N^2)\\)

#include <bits/stdc++.h> using namespace std; const int N = 20; const int INF = 1e9; int T, n, ans, rem[N], mp[N][N], surr[N][N]; int mv[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}}; bool in_map (int x, int y) { return 0 <= x && x < n && 0 <= y && y < n; } void add_ele (int x, int y) { // printf ("add (%d, %d)\n", x, y); for (int k = 0; k < 4; ++k) { int tx = x + mv[k][0]; int ty = y + mv[k][1]; if (in_map (tx, ty)) { // printf ("surr[%d][%d]++\n", tx, ty); surr[tx][ty] += 1; } } } int get_ans (int sit, int prew) { // cout << "sit = " << sit << endl; // sit -> 上一行的状态 int ret = 0; // cout << "sit = " << sit << endl; memset (surr, 0, sizeof (surr)); for (int i = 0; i < n; ++i) { if (sit & (1 << i)) add_ele (0, i); } // for (int i = 0; i < n; ++i) { // for (int j = 0; j < n; ++j) { // printf ("%d ", surr[i][j]); // } // printf ("\n"); // } for (int i = 1; i < n; ++i) { for (int j = 0; j < n; ++j) { // printf ("surr[%d - 1][%d] = %d, mp[%d][%d] = %d\n", i, j, surr[i - 1][j], i, j, mp[i][j]); if (mp[i][j] == 1) add_ele (i, j); if (surr[i - 1][j] % 2 == 1) { if (mp[i][j] == 1) return INF; add_ele (i, j); ret++; } } } // cout << "ret = " << ret << " w = " << prew << endl; return ret + prew; } void dfs (int i, int w, int sit) { if (i == rem[0] + 1) { ans = min (ans, get_ans (sit, w)); return; } dfs (i + 1, w + 1, sit | (1 << rem[i])); dfs (i + 1, w + 0, sit | (0 << rem[i])); } int main () { // freopen ("data.in", "r", stdin); cin >> T; for (int Case = 1; Case <= T; ++Case) { ans = INF; cin >> n; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cin >> mp[i][j]; } } int ini = 0; memset (rem, 0, sizeof (rem)); for (int i = 0; i < n; ++i) { if (!mp[0][i]) rem[++rem[0]] = i; ini |= (mp[0][i] << i); } dfs (1, 0, ini); cout << "Case " << Case << ": " << (ans == INF ? -1 : ans) << endl; } }

--------------------

> 例题\\(8\\) 彩色立方体（\\(LA3401\\)）

*  编写关键在于确定每一个立方体可以旋转成多少种形式，为每个立方体确定形态。
 *  同样是函数式编程的思想简化代码，建议提前对立方体的姿态映射打表。

#include <bits/stdc++.h> using namespace std; int dice24[24][6] = { {2, 1, 5, 0, 4, 3}, {2, 0, 1, 4, 5, 3}, {2, 4, 0, 5, 1, 3}, {2, 5, 4, 1, 0, 3}, {4, 2, 5, 0, 3, 1}, {5, 2, 1, 4, 3, 0}, {1, 2, 0, 5, 3, 4}, {0, 2, 4, 1, 3, 5}, {0, 1, 2, 3, 4, 5}, {4, 0, 2, 3, 5, 1}, {5, 4, 2, 3, 1, 0}, {1, 5, 2, 3, 0, 4}, {5, 1, 3, 2, 4, 0}, {1, 0, 3, 2, 5, 4}, {0, 4, 3, 2, 1, 5}, {4, 5, 3, 2, 0, 1}, {1, 3, 5, 0, 2, 4}, {0, 3, 1, 4, 2, 5}, {4, 3, 0, 5, 2, 1}, {5, 3, 4, 1, 2, 0}, {3, 4, 5, 0, 1, 2}, {3, 5, 1, 4, 0, 2}, {3, 1, 0, 5, 4, 2}, {3, 0, 4, 1, 5, 2}, }; const int N = 4; int n, ans, dice[N][6]; vector <string> names; int ID (const char *name) { string s = name; int n = names.size (); for (int i = 0; i < n; ++i) { if (names[i] == s) return i; } names.push_back (s); return n; } int r[N], color[N][6]; void check () { for (int i = 0; i < n; ++i) { for (int j = 0; j < 6; ++j) { color[i][dice24[r[i]][j]] = dice[i][j]; } } int tot = 0; for (int j = 0; j < 6; ++j) { int cnt[N * 6]; memset (cnt, 0, sizeof (cnt)); int maxface = 0; for (int i = 0; i < n; ++i) { maxface = max (maxface, ++cnt[color[i][j]]); } tot += n - maxface; } ans = min (ans, tot); } void dfs (int d) { if (d == n) {check (); return;} for (int i = 0; i < 24; ++i) { r[d] = i; dfs (d + 1); } } int main () { // freopen ("data.in", "r", stdin); while (cin >> n) { if (n == 0) break; names.clear (); for (int i = 0; i < n; ++i) { for (int j = 0; j < 6; ++j) { char name[30]; scanf ("%s", name); dice[i][j] = ID (name); } } ans = n * 6; r[0] = 0; dfs (1); cout << ans << endl; } }

--------------------

> 例题\\(9\\) 中国麻将（\\(UVa11210\\)）

*  暴力搜索，类似于斗地主那个题？枚举出来每一种牌型看能不能枚举完就好。

#include <bits/stdc++.h> using namespace std; string mahjong[34] = { "1T", "2T", "3T", "4T", "5T", "6T", "7T", "8T", "9T", "1S", "2S", "3S", "4S", "5S", "6S", "7S", "8S", "9S", "1W", "2W", "3W", "4W", "5W", "6W", "7W", "8W", "9W", "DONG", "NAN", "XI", "BEI", "ZHONG", "FA", "BAI" }; string s[14]; int bel[14], bin[34]; bool equals (string s1, string s2) { if (s1.length () != s2.length ()) return false; for (int i = 0; i < (int)s1.length (); ++i) { if (s1[i] != s2[i]) return false; } return true; } int id (string str) { for (int i = 0; i < 34; ++i) { if (equals (str, mahjong[i])) { return i; } } return -1; } int Case = 0; bool judge () {//剩下的是否全是3个 // printf ("In!"); for (int i = 0; i < 34; ++i) { if (bin[i] != 0 && bin[i] != 3) return false; } return true; } bool dfs (int x, int r) {//判断顺子 // printf ("x = %d, r = %d\n", x, r); if (x == r * 9) { if (x == 27) return judge (); else return dfs (x, r + 1); } int ret = false; if (x + 2 < r * 9) { if (bin[x + 0] && bin[x + 1] && bin[x + 2]) { bin[x + 0]--, bin[x + 1]--, bin[x + 2]--; ret |= dfs (x, r); bin[x + 0]++, bin[x + 1]++, bin[x + 2]++; } } ret |= dfs (x + 1, r); return ret; } bool can_use (int x) { bin[x]++; int ret = 0; // cout << endl; // for (int i = 0; i < 34; ++i) { // if (bin[i]) cout << mahjong[i] << ": " << bin[i] << endl; // } for (int i = 0; i < 34; ++i) { if (bin[i] >= 2) { bin[i] -= 2; // printf ("i = %d\n", i); for (int i = 0; i < 34; ++i) { // if (bin[i]) cout << mahjong[i] << ": " << bin[i] << endl; } ret |= dfs (0, 1); bin[i] += 2; } }//枚举将牌 bin[x]--; return ret; } int main () { // freopen ("data.in", "r", stdin); while (cin >> s[0] && s[0][0] != '0' && ++Case) { cout << "Case " << Case << ":"; memset (bin, 0, sizeof (bin)); for (int i = 1; i < 13; ++i) cin >> s[i]; for (int i = 0; i < 13; ++i) bin[bel[i] = id (s[i])]++; // printf ("can_use (12) = %d\n", can_use (12)); bool succeeded = false; for (int i = 0; i < 34; ++i) { if (bin[i] < 4 && can_use (i)) { cout << " " << mahjong[i]; succeeded = true; } } if (!succeeded) printf (" Not ready"); cout << endl; } }

--------------------

> 例题\\(10\\) 正整数序列（\\(UVa11384\\)）

*  关键在能不能想到两个\\(\[1,x\]\\)和一个\\(\[1,x\]\\)消除的步数是一样的。
 *  又因为\\(Ans(x)\\)显然单调递增，所以把一个\\(\[1,x\]\\)拆分成两个\\(\[1,ceil(x/2)\]\\)一定是最优的，递归求解即可。

#include <bits/stdc++.h> using namespace std; int n; int f (int x) { if (x <= 1) return x; return f(x / 2) + 1; } int main () { // freopen ("data.in", "r", stdin); while (cin >> n) { cout << f(n) << endl; } }

--------------------

> 例题\\(11\\) 新汉诺塔问题（\\(UVa10795\\)）

*  切入点是把盘子从大到小依次归位，已经归位的可以忽略，然后就可以考虑怎么把当前最大的未归位盘子归位。由于盘子可以倒着放回去所以过程可逆，这点很关键。
 *  详情参考蓝书。\\(LRJ\\)讲的相当清楚。

#include <bits/stdc++.h> using namespace std; #define int long long int f (int *P, int i, int final) { //f (x, y, z) -> 把状态x下[1, i]的柱子移动到final上 if (i == 0) return 0; if (P[i] == final) return f (P, i - 1, final); return f (P, i - 1, 6 - P[i] - final) + (1ll << (i - 1)); } const int N = 65; int n, start[N], finish[N]; signed main () { int Case = 0; while (cin >> n && n != 0) { for (int i = 1; i <= n; ++i) cin >> start[i]; for (int i = 1; i <= n; ++i) cin >> finish[i]; int k = n; while (k >= 1 && start[k] == finish[k]) k--; int ans = 0; if (k >= 1) { int etc = 6 - start[k] - finish[k]; ans = f (start, k - 1, etc) + f (finish, k - 1, etc) + 1; } cout << "Case " << ++Case << ": " << ans << endl; } }

--------------------

> 例题\\(12\\) 组装电脑（\\(LA3971\\)）

*  常见套路：最小值最大考虑二分。
 *  个人想法：似乎还可以做一个价格—质量排序，使价格递增时质量也单调递增，然后贪心地删除？不过好像比二分麻烦=。=
 *  二分技巧：把区间划分为可用和不可用两部分，继续二分的条件是\\(l< r\\)，使\\(mid\\)向不可用的那一个方向靠拢。

#include <bits/stdc++.h> using namespace std; const int N = 1010; const int INF = 0x3f3f3f3f; int T, n, b, tot, pri[N], val[N]; string type[N], name[N]; map <string, int> id; int cho_pri[N]; bool can_use (int minw) { //选中的物件其w要>=minw memset (cho_pri, 0x3f, sizeof (cho_pri)); for (int i = 1; i <= n; ++i) { if (val[i] >= minw) { cho_pri[id[type[i]]] = min (cho_pri[id[type[i]]], pri[i]); } } int have = b; for (int i = 1; i <= tot; ++i) { if (cho_pri[i] == INF) return false; if (have < cho_pri[i]) return false; have -= cho_pri[i]; } return true; } int main () { cin >> T; while (T--) { tot = 0; id.clear (); cin >> n >> b; for (int i = 1; i <= n; ++i) { cin >> type[i] >> name[i] >> pri[i] >> val[i]; if (!id.count (type[i])) id[type[i]] = ++tot; } int l = 0, r = 1e9 + 7; while (l < r) { int mid = (l + r + 1) >> 1; if (can_use (mid)) { l = mid; } else { r = mid - 1; } } cout << l << endl; } }

--------------------

> 例题\\(13\\) 派（\\(LA3635\\)）

*  求最大面积，实数二分。枚举对每一个整块派的划分。

#include <bits/stdc++.h> using namespace std; const int N = 10010; const double eps = 1e-5; const double pi = acos(-1); int T, n, m, r[N]; bool can_use (double s) { //每个派切出面积s,切出来个数是否>=m; int tot = 0; for (int i = 1; i <= n; ++i) { tot += floor (pi * r[i] * r[i] / s); } return tot >= m; } int main () { cin >> T; while (T--) { cin >> n >> m; ++m; for (int i = 1; i <= n; ++i) cin >> r[i]; double l = 0, r = 1e9; while (r - l > eps) { double mid = (l + r) / 2.0; if (can_use (mid)) { l = mid; } else { r = mid; } } printf ("%.4lf\n", l); } }

--------------------

> 例题\\(14\\) 填充正方形（\\(UVa11520\\)）

*  模拟，没啥难度，填就完事了。

#include <bits/stdc++.h> using namespace std; const int N = 15; int T, n; char mp[N][N]; bool surr[N][N][27]; int mv[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}}; bool in_map (int x, int y) { return 1 <= x && x <= n && 1 <= y && y <= n; } void use (int x, int y, char ch) { for (int i = 0; i < 4; ++i) { int tx = x + mv[i][0]; int ty = y + mv[i][1]; if (in_map (tx, ty)) { // printf ("surr (%d, %d, %d) = true\n", tx, ty, ch - 'A'); surr[tx][ty][ch - 'A'] = true; } } } int main () { // freopen ("data.in", "r", stdin); // freopen ("data.out", "w", stdout); cin >> T; for (int Case = 1; Case <= T; ++Case) { cout << "Case " << Case << ":" << endl; cin >> n; memset (surr, 0, sizeof (surr)); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { cin >> mp[i][j]; if (mp[i][j] != '.') { use (i, j, mp[i][j]); } } } for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (mp[i][j] == '.') { for (int k = 0; k < 5; ++k) { if (!surr[i][j][k]) { use (i, j, 'A' + k); mp[i][j] = 'A' + k; break; } } } putchar (mp[i][j]); } putchar ('\n'); } } }

--------------------

> 例题\\(15\\) 网络（\\(LA3902\\)）

*  和\\(Luogu\\)上那个消防局的设立是一样的。。
 *  有根树转无根树，每次取深度最大的叶子节点的\\(k\\)级祖先，删除其周边节点。正确性显然。
 *  复杂度\\(O(NlogN)\\)（但后来我倍增挂了就变成\\(O(N^2logN)\\)了）
 *  注意注意注意要判断叶子！

#include <bits/stdc++.h> using namespace std; const int N = 100010; int T, n, s, k, cnt, head[N]; int du[N]; struct edge { int nxt, to; }e[N << 1]; void add_len (int u, int v) { e[++cnt] = (edge) {head[u], v}; head[u] = cnt; e[++cnt] = (edge) {head[v], u}; head[v] = cnt; } struct Node { int p, d; bool operator < (Node rhs) const { return d < rhs.d; } }; priority_queue <Node> q; int deep[N], pre[N]; void dfs (int u, int fa, int d) { pre[u] = fa; if (d > k && du[u] == 1) { q.push ((Node) {u, d}); // printf ("u = %d, deep[u] = %d\n", u, deep[u]); } for (int i = head[u]; i; i = e[i].nxt) { // printf ("%d -> %d\n", u, e[i].to); int v = e[i].to; if (v != fa) { dfs (v, u, d + 1); } } } bool vis[N]; void take_place (int u, int d, int fa) { vis[u] = true; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v != fa && d < k) { take_place (v, d + 1, u); } } } int main () { // freopen ("data.in", "r", stdin); // freopen ("data.out", "w", stdout); cin >> T; while (T--) { cnt = 0; memset (du, 0, sizeof (du)); memset (vis, 0, sizeof (vis)); memset (head, 0, sizeof (head)); cin >> n >> s >> k; for (int i = 1; i <= n - 1; ++i) { static int u, v; cin >> u >> v; add_len (u, v); du[u]++, du[v]++; } dfs (s, 0, 0); int ans = 0; while (!q.empty ()) { int u = q.top ().p; q.pop (); if (vis[u]) continue; ans = ans + 1; for (int i = 0; i < k; ++i) u = pre[u]; take_place (u, 0, 0); } cout << ans << endl; } }

--------------------

> 例题\\(16\\) 长城守卫（\\(LA3177\\)）

*  偶数的时候很好办，奇数的时候就是一个很巧妙的构造思想了。
 *  我们先假设第一个人选了\\(\[1,r\_1\]\\)这些礼物，只要让其他偶数位尽可能靠前，奇数位尽可能靠后，我们\\(1\\)和\\(N\\)就可以尽可能保证不相交。比较绕的一点在于要记录第\\(i\\)个人选了\\(\[1,r\_1\]\\)的部分有多少，选了\\(\[r\_1+1,N\]\\)的部分有多少。这里我们二分一个最小值，使之满足第\\(N\\)个人不会在\\(\[1,r\_1\]\\)部分选择即为合法。

#include <bits/stdc++.h> using namespace std; const int N = 100010; const int INF = 0x3f3f3f3f; int n, r[N], Ltot[N], Rtot[N]; bool can_use (int tot) { int x = r[1], y = tot - r[1]; Ltot[1] = x, Rtot[1] = 0; for (int i = 2; i <= n; ++i) { if (i % 2 == 1) {//奇数(往后取) Rtot[i] = min (y - Rtot[i - 1], r[i]); Ltot[i] = r[i] - Rtot[i]; } else { Ltot[i] = min (x - Ltot[i - 1], r[i]); Rtot[i] = r[i] - Ltot[i]; } } return Ltot[n] == 0; } int main () { while (cin >> n && n) { for (int i = 1; i <= n; ++i) cin >> r[i]; if (n == 1) { cout << r[1] << endl; continue; } r[n + 1] = r[1]; int L = 0, R = INF; for (int i = 1; i <= n; ++i) { L = max (L, r[i] + r[i + 1]); } if (n % 2 == 0) { cout << L << endl; } else { while (L < R) { int mid = (L + R) >> 1; if (can_use (mid)) { R = mid; } else { L = mid + 1; } } cout << R << endl; } } }

--------------------

> 例题\\(17\\) 年龄排序（\\(UVa11462\\)）

*  桶排序板子，注意性能优化。

#include <bits/stdc++.h> using namespace std; int read () { int s = 0, w = 1, ch = getchar (); while ('9' < ch || ch < '0') { s = s * 10 + ch - '0'; ch = getchar (); } while ('0' <= ch && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar (); } return s * w; } int n; short bin[110]; int main () { while ((n = read()) != 0) { memset (bin, 0, sizeof (bin)); for (int i = 1; i <= n; ++i) bin[read ()]++; bool first = true; for (int i = 1; i <= 100; ++i) { for (int j = 1; j <= bin[i]; ++j) { if (!first) putchar (' '); printf ("%d", i); first = false; } } printf ("\n"); } }

--------------------

> 例题\\(18\\) 开放式学分制（\\(UVa11078\\)）

*  最开始学傻了糊了一个\\(RMQ\\)上去，后来才意识到维护一个前缀最大和后缀最小就可以了=\_=太懒了代码就没换写法

#include <bits/stdc++.h> using namespace std; const int N = 100010; const int INF = 1e9; int T, n, arr[N]; namespace RMQ { int maxw[N][20], minw[N][20]; void Init () { for (int i = 1; i <= n; ++i) { maxw[i][0] = minw[i][0] = arr[i]; } for (int i = 1; (1 << i) <= n; ++i) { for (int j = 1; j + (1 << i) - 1 <= n; ++j) { maxw[j][i] = max (maxw[j][i - 1], maxw[j + (1 << (i - 1))][i - 1]); minw[j][i] = min (minw[j][i - 1], minw[j + (1 << (i - 1))][i - 1]); } } } int query_max (int l, int r) { int mx = log2 (r - l + 1); return max (maxw[l][mx], maxw[r - (1 << mx) + 1][mx]); } int query_min (int l, int r) { int mx = log2 (r - l + 1); return min (minw[l][mx], minw[r - (1 << mx) + 1][mx]); } } int main () { cin >> T; while (T--) { cin >> n; for (int i = 1; i <= n; ++i) cin >> arr[i]; RMQ :: Init (); int ans = -INF; for (int i = 1; i < n; ++i) { ans = max (ans, RMQ :: query_max (1, i) - RMQ :: query_min (i + 1, n)); } cout << ans << endl; } }

--------------------

> 例题\\(19\\) 计算器谜题（\\(UVa11549\\)）

*  \\(Floyd\\)判圈算法。形象来说就是只要有圈的话，一个每次跑一步，一个每次跑两步。在追上的时候，这个圈就被确定存在并且枚举完了。原题在一个范围似乎不会太大的剩余系里面，所以一定有圈。复杂度\\(O(N\*k = 能过)(0<k<1)\\)

#include <bits/stdc++.h> using namespace std; int T, n, k; long long _pow[20]; int _nxt (int x) { if (x == 0) return 0; int wei = log10 (1ll * x * x) + 1; //位数 // cout << "wei_" << x << " = " << wei << endl return 1ll * x * x / _pow[max (wei - n, 0)]; } int main () { // freopen ("data.in", "r", stdin); cin >> T; _pow[0] = 1; for (int i = 1; i <= 18; ++i) { _pow[i] = _pow[i - 1] * 10; } while (T--) { cin >> n >> k; int k1 = k, k2 = k, ans = k; do { k1 = _nxt (k1); ans = max (ans, k1); k2 = _nxt (k2); ans = max (ans, k2); k2 = _nxt (k2); ans = max (ans, k2); } while (k1 != k2); cout << ans << endl; } }

略困，今晚先更新到这。——\\(2019\\)年\\(04\\)月\\(15\\)日\\(23:43:37\\)

--------------------

> 例题\\(20\\)  流星（\\(LA3905\\)）

*  算是计算几何吧。。。实际上挺简单的。用了扫描的思想。
 *  每一个流星表示成一个初始点和一个速度的向量，实际上最后还是在时间轴上取一段连续的时间覆盖上去。

#include <bits/stdc++.h> using namespace std; const int N = 100010; const double eps = 1e-8; const int INF = 0x7fffffff; int T, n, w, h; double sl[N], sr[N]; struct Element { double pos; int val; bool operator < (Element rhs) const { return pos < rhs.pos; } }ele[N << 1]; int main () { cin >> T; while (T--) { int tot = 0; cin >> w >> h >> n; for (int i = 1; i <= n; ++i) { static int x, y, vx, vy; cin >> x >> y >> vx >> vy; double lx, rx, ly, ry; if (vx > 0) lx = max ((double)(0 - x) / vx, 0.0), rx = max ((double)(w - x) / vx, 0.0); if (vx < 0) lx = max ((double)(w - x) / vx, 0.0), rx = max ((double)(0 - x) / vx, 0.0); if (vx == 0) {if (0 < x && x < w) lx = 0, rx = INF; else lx = rx = 0;} if (vy > 0) ly = max ((double)(0 - y) / vy, 0.0), ry = max ((double)(h - y) / vy, 0.0); if (vy < 0) ly = max ((double)(h - y) / vy, 0.0), ry = max ((double)(0 - y) / vy, 0.0); if (vy == 0) {if (0 < y && y < h) ly = 0, ry = INF; else ly = ry = 0;} double l = max (lx, ly), r = min (rx, ry); if (r - l > eps) { ele[++tot] = (Element) {l, +1}; ele[++tot] = (Element) {r, -1}; } } int res = 0, ans = 0; sort (ele + 1, ele + 1 + tot); for (int i = 1; i <= tot; ++i) { res += ele[i].val; while (ele[i].pos == ele[i + 1].pos) { res += ele[++i].val; } ans = max (ans, res); } cout << ans << endl; } }

--------------------

> 例题\\(21\\)  子序列（\\(LA2678\\)）

*  题目本身很简单，厉害的是它的思想。
 *  解法\\(1\\)：直接二分
    
     *  算法显然。复杂度\\(O(NlogN)\\)
 *  解法\\(2\\)：考虑枚举。
    
     *  最简单的，可以\\(O(N^3)\\)枚举每一个子段，用前缀和可以优化到\\(O(N^2)\\)
     *  注意到对于每一个\\(r\\)，只有一个\\(l\\)可能会对答案产生贡献，而且这个\\(l\\)的位置单调递增（因为是正整数序列），所以枚举就变成了\\(O(N)\\)的，每个\\(l\\)最多被作为左端点被扫到一遍。
     *  懒省事就没特判。。详见代码=\_=

#include <bits/stdc++.h> using namespace std; const int N = 100010; int n, s, sumw[N]; int read () { int s = 0, ch = getchar (); while ('9' < ch || ch < '0') { ch = getchar (); } while ('0' <= ch && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar (); } return s; } int main () { while (cin >> n >> s) { for (int i = 1; i <= n; ++i) sumw[i] = sumw[i - 1] + read (); int minlen = n + 1; for (int r = 1, l = 1; r <= n; ++r) { if (sumw[r] - sumw[l - 1] >= s) { while (sumw[r] - sumw[l - 1] >= s) ++l; --l; minlen = min (minlen, r - l + 1); } } cout << minlen % (n + 1) << endl; } }

--------------------

> 例题\\(22\\) 最大子矩阵（\\(LA3029\\)）

*  题意：含障碍网格图，求最大子矩阵。
 *  解法：悬线法，扫描的思想，详见代码。

#include <bits/stdc++.h> using namespace std; const int N = 1010; int mat[N][N], up[N][N], ll[N][N], rr[N][N]; int T, m, n; int main () { cin >> T; while (T--) { cin >> m >> n; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { int ch = getchar (); while (ch != 'F' && ch != 'R') ch = getchar (); mat[i][j] = ch == 'F' ? 0 : 1; } } int ans = 0; for (int i = 0; i < m; ++i) { int lo = -1, ro = n; for (int j = 0; j < n; ++j) { if (mat[i][j] == 1) { up[i][j] = ll[i][j] = 0; lo = j; } else { up[i][j] = i == 0 ? 1 : up[i - 1][j] + 1; ll[i][j] = i == 0 ? lo + 1 : max (ll[i - 1][j], lo + 1); } } for (int j = n - 1; j >= 0; --j) { if (mat[i][j] == 1) { rr[i][j] = n; ro = j; } else { rr[i][j] = i == 0 ? ro - 1 : min (rr[i - 1][j], ro - 1); ans = max (ans, up[i][j] * (rr[i][j] - ll[i][j] + 1)); } } } cout << ans * 3 << endl; } }

--------------------

> 例题\\(23\\) 遥远的银河（\\(LA3695\\)）

*  题意：找一个矩形，使其**边界上**包括尽可能多的点。
 *  解法：枚举矩形。
    
     *  \\(O(N^5)\\)朴素枚举矩形每一条边
     *  考虑固定一些限制条件，比如只枚举上下边界，对左右边的位置想办法优化维护一下。我们列出来要维护的最大值，用扫描的思想去搞一下就可以了，难度在于细节。

#include <bits/stdc++.h> using namespace std; const int N = 100 + 10; struct Point { int x, y; bool operator < (Point rhs) const { return x < rhs.x; } }P[N]; int n, m, y[N], on[N], on2[N], rem[N]; int solve () { sort (P, P + n); sort (y, y + n); m = unique (y, y + n) - y; if (m <= 2) return n; int ans = 0; for (int a = 0; a < m; ++a) { for (int b = a + 1; b < m; ++b) { int k = 0, ly = y[a], ry = y[b]; for (int i = 0; i < n; ++i) { if (i == 0 || P[i].x != P[i - 1].x) { // 新的竖线 ++k; on[k] = on2[k] = 0; rem[k] = rem[k - 1] + on2[k - 1] - on[k - 1]; } if (P[i].y > ly && P[i].y < ry) on[k]++; if (P[i].y >= ly && P[i].y <= ry) on2[k]++; } if (k <= 2) return n; int M = 0; for (int j = 1; j <= k; ++j) { ans = max (ans, rem[j] + on2[j] + M); M = max (M, on[j] - rem[j]); } } } return ans; } int main () { int kase = 0; while (cin >> n && n) { for (int i = 0; i < n; ++i) { cin >> P[i].x >> P[i].y; y[i] = P[i].y; } printf ("Case %d: %d\n", ++kase, solve ()); } }

--------------------

> 例题\\(24\\) 废料堆（\\(UVa10755\\)）

*  三维立方体，每一块\\((x, y, z)\\)有一个整数价值，求最大价值子立方体。\\(Tips:N <= 20。\\)
 *  高维题目考虑降维。
    
     *  一维时我们有\\(O(N)\\)的最大子段和解法。
     *  二维的时候我们可以枚举某些连续的行，把这些行压成一个一维序列做最大子段和，复杂度\\(O(N^3)\\)
     *  三维的时候我们可以枚举某些连续的高，把这些搞压成一个二维矩形做最大子矩阵，复杂度\\(O(N^5)\\)

#include <bits/stdc++.h> using namespace std; #define int long long const int N = 20 + 5; const int INF = 1e18; int T, n, m, h, line[N], mat[N][N], w[N][N][N], sumh[N][N][N], sumy[N][N], sumx[N]; int solve_1D () { int now = -INF, ans = -INF; for (int i = 1; i <= n; ++i) { now = max (line[i], now + line[i]); ans = max (ans, now); } return ans; } int solve_2D () { for (int x = 1; x <= n; ++x) { for (int y = 1; y <= m; ++y) { sumy[x][y] = sumy[x][y - 1] + mat[x][y]; } } int ans = -INF; for (int ly = 1; ly <= m; ++ly) { for (int ry = ly; ry <= m; ++ry) { for (int x = 1; x <= n; ++x) { line[x] = sumy[x][ry] - sumy[x][ly - 1]; } ans = max (ans, solve_1D ()); } } return ans; } int solve_3D () { for (int x = 1; x <= n; ++x) { for (int y = 1; y <= m; ++y) { for (int z = 1; z <= h; ++z) { sumh[x][y][z] = sumh[x][y][z - 1] + w[x][y][z]; } } } int ans = -INF; for (int lz = 1; lz <= h; ++lz) { for (int rz = lz; rz <= h; ++rz) { for (int x = 1; x <= n; ++x) { for (int y = 1; y <= m; ++y) { mat[x][y] = sumh[x][y][rz] - sumh[x][y][lz - 1]; } } //压成一个平面 ans = max (ans, solve_2D ()); } } return ans; } signed main () { // freopen ("data.in", "r", stdin); cin >> T; while (T--) { cin >> n >> m >> h; int x = 1, y = 1, z = 1; for (int i = 1; i <= n * m * h; ++i, ++z) { if (z > h) y += 1, z -= h; if (y > m) x += 1, y -= m; cin >> w[x][y][z]; } cout << solve_3D () << endl; if (T) cout << endl; } }

--------------------

> 例题\\(25\\) 侏罗纪（\\(LA2965\\)）

*  题意：\\(N\\)个字符串，选择尽可能多的串，使每个字母都可以出现偶数次。\\(Tips:N<=24。\\)
 *  解法：折半搜索。因为两部分的可用答案具有可以对应的性质（字母个数对应起来是偶数），合并答案时可以开一个桶（\\(Map\\)）来记录。复杂度\\(O(2^N)->O(2^\{N/2\}logN)\\)

#include <bits/stdc++.h> using namespace std; const int N = 24 + 5; const int M = 1000000 + 5; #define lowbit(x) (x & -x) int n, val[N]; char s[M]; map <int, int> mp; int wei (int x) { int s = 0; while (x) x -= lowbit (x), ++s; return s; } void dfs1 (int now, int cho, int sit) { if (now == n / 2 + 1) { // cout << "sit = " << sit << endl; mp[sit] = wei (mp[sit]) > wei (cho) ? mp[sit] : cho; // cout << "mp[sit] = " << mp[sit] << endl; // cout << "wei[sit] = " << wei (sit) << endl; return; } dfs1 (now + 1, cho, sit); dfs1 (now + 1, cho | (1 << now), sit ^ val[now]); } int ans, fin; void dfs2 (int now, int cho, int sit) { if (now == n) { // cout << "find : sit = " << sit << endl; if (mp.count (sit)) { if (ans < wei (cho) + wei (mp[sit])) { // cout << "cho = " << cho << " mp[sit] = " << mp[sit] << endl; fin = cho | mp[sit]; ans = wei (cho) + wei (mp[sit]); } } return; } dfs2 (now + 1, cho, sit); dfs2 (now + 1, cho | (1 << now), sit ^ val[now]); } int main () { // freopen ("data.in", "r", stdin); while (cin >> n && n) { mp.clear (); ans = fin = 0; memset (val, 0, sizeof (val)); for (int i = 0; i < n; ++i) { cin >> s; int l = strlen (s); for (int j = 0; j < l; ++j) { val[i] ^= (1 << (s[j] - 'A')); } // cout << "val[" << i << "] = " << val[i] << endl; } dfs1 (0, 0, 0); dfs2 (n / 2 + 1, 0, 0); cout << ans << endl; for (int i = 0; i < n; ++i) { if ((fin >> i) & 1) printf ("%d ", i + 1); } cout << endl; } }

--------------------

> 例题\\(26\\) 约瑟夫问题的变形（\\(LA3882\\)）

*  题意：给你一个环，在上面做约瑟夫，求**最后一个被删除的数**。\\(n, k <=10000\\)
 *  因为只关心最后一个被删除的数，所以可以不考虑中间的直接进行递推。
 *  设一共有\\(\[0,i-1\]\\)这\\(i\\)个时，从\\(0\\)开始选择删除的最后一个数是\\(f(i)\\)。那么有\\(f(1) = 0,f(x) =(f(x-1)+k)\\%n。\\)
 *  考虑方法：删除一个数后对剩下的再编号。

#include <bits/stdc++.h> using namespace std; const int N = 10010; int n, m, k, f[N]; int main () { // freopen ("data.in", "r", stdin); while (cin >> n >> k >> m && n) { for (int i = 2; i <= n; ++i) f[i] = (f[i - 1] + k) % i; int ans = (m - k + 1 + f[n]) % n; if (ans <= 0) ans += n; cout << ans << endl; } }

--------------------

> 例题\\(27\\) 王子和公主（\\(UVa10635\\)）

*  题意：两个不含重复元素的序列，求最长公共子序列。
 *  解法：对第二个序列**以第一个序列内的元素编号为关键字**进行排序，转化为求最长上升子序列。

#include <bits/stdc++.h> using namespace std; const int N = 100010; int T, n, p, q, A1[N], A2[N], id[N], arr[N]; int main () { // freopen ("data.in", "r", stdin); cin >> T; for (int Case = 1; Case <= T; ++Case) { cin >> n >> p >> q; ++p, ++q; memset (id, 0, sizeof (id)); memset (arr, 0, sizeof (arr)); for (int i = 1; i <= p; ++i) { cin >> A1[i]; id[A1[i]] = i; } for (int i = 1; i <= q; ++i) { cin >> A2[i]; if (!id[A2[i]]) { q = q - 1; i = i - 1; } else { A2[i] = id[A2[i]]; } } int tot = 0; for (int i = 1; i <= q; ++i) { if (A2[i] > arr[tot]) arr[++tot] = A2[i]; else { arr[lower_bound (arr + 1, arr + 1 + tot, A2[i]) - arr] = A2[i]; } } cout << "Case " << Case << ": " << tot << endl; } }

--------------------

> 例题\\(28\\) \\(Sum游戏\\)（\\(UVa10891\\)）

*  记忆化搜索的写法很显然，枚举每种后继状态做一个\\(max\\)，记忆化一下就有\\(O(N^3)\\)了。
 *  考虑每个状态\\((i,j)\\)（剩余\\(\[i,j\]\\)这一段）的决策实际上是对状态矩阵中的\\(\[i,i->j-1\]\\)和\\(\[i+1->j,j\]\\)这两段取\\(min\\)作为舍弃的收益减掉，也就是说我们维护一下这两个最小值的矩阵，就可以做到\\(O(N)\\)转移了。

//我自己的写法 #include <bits/stdc++.h> using namespace std; const int N = 100 + 5; const int INF = 0x3f3f3f3f; int n, sum[N], dp[N][N][2]; int dfs (int l, int r, int p) { // player p -> can choose [l, r]; int ans = -INF; if (l > r) return 0; if (dp[l][r][p] != INF) return dp[l][r][p]; for (int i = l; i <= r; ++i) { ans = max (ans, -dfs (i + 1, r, p ^ 1) + sum[i] - sum[l - 1]); // choose [l, i] ans = max (ans, -dfs (l, i - 1, p ^ 1) + sum[r] - sum[i - 1]); // choose [i, r] } return dp[l][r][p] = ans; } int main () { while (cin >> n && n) { memset (dp, 0x3f, sizeof (dp)); for (int i = 1; i <= n; ++i) { cin >> sum[i]; sum[i] += sum[i - 1]; } cout << dfs (1, n, 0) << endl; } }

//蓝书上的易于优化的记搜写法 #include <bits/stdc++.h> using namespace std; const int N = 100 + 5; const int INF = 0x3f3f3f3f; int n, sum[N], dp[N][N]; int dfs (int l, int r) { // player p -> can choose [l, r]; int ans = 0; if (l > r) return 0; if (dp[l][r] != INF) return dp[l][r]; for (int i = l; i < r; ++i) ans = min (ans, dfs (i + 1, r)); // choose [l, i] for (int i = r; i > l; --i) ans = min (ans, dfs (l, i - 1)); return dp[l][r] = sum[r] - sum[l - 1] - ans; } int main () { // freopen ("data.in", "r", stdin); while (cin >> n && n) { memset (dp, 0x3f, sizeof (dp)); for (int i = 1; i <= n; ++i) { cin >> sum[i]; sum[i] += sum[i - 1]; } cout << 2 * dfs (1, n) - sum[n] << endl; } }

//O(N^2)最优解法 #include <bits/stdc++.h> using namespace std; const int N = 100 + 5; int n, A[N], sum[N], f[N][N], g[N][N], dp[N][N]; int main () { // freopen ("data.in", "r", stdin); while (cin >> n && n) { for (int i = 1; i <= n; ++i) { cin >> A[i]; sum[i] = sum[i - 1] + A[i]; f[i][i] = g[i][i] = dp[i][i] = A[i]; } for (int L = 1; L < n; ++L) { for (int i = 1; i + L <= n; ++i) { int j = i + L, m = 0; m = min (m, f[i + 1][j]); m = min (m, g[i][j - 1]); dp[i][j] = sum[j] - sum[i - 1] - m; f[i][j] = min (dp[i][j], f[i + 1][j]); g[i][j] = min (dp[i][j], g[i][j - 1]); } } cout << 2 * dp[1][n] - sum[n] << endl; } }

--------------------

> 例题\\(29\\) 黑客的攻击（\\(UVa11825\\)）

*  数学模型：把\\(n\\)个集合\\(P\_1,P\_2...P\_n\\)分成尽量多组，使每组中所有集合的并等于全集。
 *  考虑二进制状态压缩，然后对分组后的集合进行\\(DP\\)。
 *  关键思想：用集合的思想去设状态。复杂度不会证。
 *  这里有[我当时写的更详细的题解][Link 1]。

#include <bits/stdc++.h> using namespace std; const int N = 20; int Case, n, m, to, s[N], f[N], cho[1 << N]; int main () { // freopen ("data.in", "r", stdin); while (cin >> n && n) { for (int i = 0; i < n; ++i) { cin >> m; s[i] = 1 << i; for (int j = 0; j < m; ++j) { cin >> to; s[i] |= 1 << to; } // cout << "s[" << i << "] = " << s[i] << endl; } const int All = (1 << n) - 1; for (int i = 0; i < 1 << n; ++i) { cho[i] = 0; for (int k = 0; k < n; ++k) { if ((i >> k) & 1) { cho[i] |= s[k]; } } } f[0] = 0; for (int S = 1; S < (1 << n); ++S) { f[S] = 0; for (int S0 = S; S0; S0 = (S0 - 1) & S) { //枚举S的子集 if (cho[S0] == All) { f[S] = max (f[S], f[S ^ S0] + 1); } } } cout << "Case " << ++Case << ": " << f[All] << endl; } }

--------------------

> 例题\\(31\\) 捡垃圾的机器人（\\(LA3983\\)）

*  解法：因为要选择的元素有序，所以可以把原\\(n\\)个元素分成连续的\\(k\\)段（不用显式建出这\\(k\\)段分段），可以推出来一个\\(O(能过)\\)的方程。（吐槽一句：因为\\(C\\)实在太小了，不知道出题人想卡什么...）
 *  正解：上面那个转移方程是可以单调队列优化的形式，套个单调队列上去就\\(O(N)\\)了。
 *  吐槽：\\(cin\\)恐成最大受害者。

//暴力 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 100010; int T, n, c, x[N], y[N], w[N], sumd[N], sumw[N], dp[N]; int dis (int i) {return x[i] + y[i];} signed main () { cin >> T; while (T--) { cin >> c >> n; memset (sumw, 0, sizeof (sumw)); memset (sumd, 0, sizeof (sumd)); for (int i = 1; i <= n; ++i) { cin >> x[i] >> y[i] >> w[i]; sumw[i] = sumw[i - 1] + w[i]; sumd[i] = sumd[i - 1] + abs (x[i] - x[i - 1]) + abs (y[i] - y[i - 1]); } memset (dp, 0x3f, sizeof (dp)); dp[0] = 0; for (int i = 1; i <= n; ++i) { for (int j = i - 1; j >= 0; --j) { if (sumw[i] - sumw[j] > c) break; // printf ("dp[%I64d] <- dp[%I64d] = %I64d\n", i, j, dp[j]); // printf (" <- dis(%I64d) = %I64d\n", i, dis (i)); // printf (" <- dis(%I64d) = %I64d\n", j + 1, dis (j + 1)); // printf (" <- sumd (%I64d -> %I64d) = %I64d\n", j + 1, i, sumd[i] - sumd[j + 1]); dp[i] = min (dp[i], dp[j] + dis (i) + dis (j + 1) + sumd[i] - sumd[j + 1]); } // cout << "dp[" << i << "] = " << dp[i] << endl; } cout << dp[n] << endl; if (T) cout << endl; } }

//正解 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 100010; int T, n, c, x[N], y[N], w[N], sumd[N], sumw[N], dp[N]; int dis (int i) {return x[i] + y[i];} struct Node { int pos, val; }q[N]; int head, tail; void Insert (int pos) { int val = dp[pos] + dis (pos + 1) - sumd[pos + 1]; while (head <= tail && q[tail].val >= val) --tail; q[++tail] = (Node) {pos, val}; } int front (int pos) { while (head <= tail && sumw[pos] - sumw[q[head].pos] > c) ++head; return q[head].val; } signed main () { // freopen ("data.in", "r", stdin); cin >> T; while (T--) { cin >> c >> n; memset (sumw, 0, sizeof (sumw)); memset (sumd, 0, sizeof (sumd)); for (int i = 1; i <= n; ++i) { cin >> x[i] >> y[i] >> w[i]; sumw[i] = sumw[i - 1] + w[i]; sumd[i] = sumd[i - 1] + abs (x[i] - x[i - 1]) + abs (y[i] - y[i - 1]); } head = 1, tail = 0; dp[0] = 0; Insert (0); for (int i = 1; i <= n; ++i) { // for (int j = i - 1; j >= 0; --j) { // if (sumw[i] - sumw[j] > c) break; // printf ("dp[%I64d] <- dp[%I64d] = %I64d\n", i, j, dp[j]); // printf (" <- dis(%I64d) = %I64d\n", i, dis (i)); // printf (" <- dis(%I64d) = %I64d\n", j + 1, dis (j + 1)); // printf (" <- sumd (%I64d -> %I64d) = %I64d\n", j + 1, i, sumd[i] - sumd[j + 1]); // dp[i] = min (dp[i], dp[j] + dis (i) + dis (j + 1) + sumd[i] - sumd[j + 1]); // } // cout << "dp[" << i << "] = " << dp[i] << endl; dp[i] = dis (i) + sumd[i] + front (i); Insert (i); } cout << dp[n] << endl; if (T) cout << endl; } }

--------------------

> 例题\\(32\\) 分享巧克力（\\(LA4794\\)）

*  题意：\\(N\*M\\)的矩形，每次可以用一条直线把它划分成两部分，问能不能切成面积为\\(a\_1,a\_2...a\_n\\)的\\(n\\)个矩形部分。
 *  考虑记搜，设状态\\(f(r,c,S)\\)，表示\\(r\*c\\)的矩形是否能恰好划分为\\(S\\)集合中的所有矩形，然后就是一个枚举子集的记搜题目了。

#include <bits/stdc++.h> using namespace std; const int M = 15 + 1; const int N = 100 + 5; int n, x, y, kase, p[N], sum[1 << M]; bool dp[N][1 << M], vis[N][1 << M]; int bitcount (int x) { return x == 0 ? 0 : bitcount (x >> 1) + (x & 1); } bool dfs (int x, int S) { if (vis[x][S]) return dp[x][S]; if (bitcount (S) == 1) return true; int y = sum[S] / x; vis[x][S] = true; for (int S0 = S & (S - 1); S0; S0 = S & (S0 - 1)) { int S1 = S ^ S0; // 拆分成两个集合 S 和 S0 if (sum[S0] % x == 0) { if (dfs (min (x, sum[S0] / x), S0) && dfs (min (x, sum[S1] / x), S1)) { return dp[x][S] = true; } } if (sum[S0] % y == 0) { if (dfs (min (y, sum[S0] / y), S0) && dfs (min (y, sum[S1] / y), S1)) { return dp[x][S] = true; } } } return dp[x][S] = false; } int main () { // freopen ("data.in", "r", stdin); while (cin >> n && n) { cin >> x >> y; memset (dp, 0, sizeof (dp)); memset (vis, 0, sizeof (vis)); memset (sum, 0, sizeof (sum)); for (int i = 0; i < n; ++i) cin >> p[i]; for (int i = 0; i < (1 << n); ++i) { for (int k = 0; k < n; ++k) { if (i & (1 << k)) sum[i] += p[k]; } } int All = (1 << n) - 1; if (sum[All] != x * y || sum[All] % x != 0) { cout << "Case " << ++kase << ": " << "No" << endl; } else { cout << "Case " << ++kase << ": " << (dfs (min (x, y), All) ? "Yes" : "No") << endl; } } }

--------------------

\\(QQ:757973845\\)。博主学习时比较仓促，博客中不清晰处，错误之处，还请指正：）

转载于:https://www.cnblogs.com/maomao9173/p/10713925.html

[Link 1]: https://www.cnblogs.com/maomao9173/p/10688004.html