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];
}
|