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