「2021CCPC华为云挑战赛」[HDU 7089] CDN流量调度问题

「题意」

给定 $n,m$ 和长为 $n$ 的正整数序列 $a,b$,求 $\sum\limits_{i=1}^{n}{\lceil{\frac{a_i}{k_i}}\rceil}$ 的最小值,满足 $1\leq k_i\leq b_i$,且 $\sum{(k_i-1)}\leq m$。

$n\leq 100, m\leq 10000, a_i\leq 10000$

「链接」

7089

「分析」

定义 $f_{i,j}$ 表示对于前 $i$ 个数,$\sum{(k_p-1)}\leq j$ 所得到的 $\sum{\lceil{\frac{a_p}{k_p}}\rceil}$ 的最小值。

显然很多状态是「废」的,因为如果增大 $k_j$ 不会使得 $\lceil{\frac{a_p}{k_p}}\rceil$ 缩小,那么这是没有意义的。

因此有意义的状态就是 $\lceil{\frac{a_p}{k_p}}\rceil$ 有不同取值的最小的 $k_p$,而这样的 $k_p$ 一共只有 $O(\sqrt{a_p})$ 个。

因此可以『整数分块』预处理出 $1\sim 10000$ 对应的所有 $k$,转移时只考虑这些值。

复杂度 $O(nm\sqrt{a_i})$。

「代码」

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
/*
* @date:
* @source:
*/
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define fir first
#define sec second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)x.size()
#define up(i, l, r) for (int i = l; i <= r; ++i)
#define dn(i, l, r) for (int i = l; i >= r; --i)
#define Trav(i, x) for (auto & i : x)
#define pb push_back
template<class T, class G> bool chkMax(T &x, G y) {
return y > x ? x = y, 1 : 0;
}
template<class T, class G> bool chkMin(T &x, G y) {
return y < x ? x = y, 1 : 0;
}

const int MAXN = 100 + 5;
const int MAXM = 10000 + 5;

int N, M;
vector<pii> Pre[MAXM];
int A[MAXN], B[MAXN];
int F[MAXN][MAXM];

void init() {
for (int i = 0; i <= 10000; ++i) {
for (int l = 1, r; l <= i; l = r + 1) {
r = i / (i / l);
Pre[i + 1].pb({l, i / l + 1});
}
Pre[i + 1].pb({i + 1, 1});
}
}

void solve() {
cin >> N >> M;
for (int i = 1; i <= N; ++i) cin >> A[i];
for (int i = 1; i <= N; ++i) cin >> B[i];
memset(F, 0x3f, sizeof F);
F[0][0] = 0;
for (int i = 1; i <= N; ++i) {
F[i][0] = F[i - 1][0] + A[i];
for (int j = 1; j <= M; ++j) {
Trav(x, Pre[A[i]]) {
if (x.fir > B[i] || j - x.fir + 1 < 0) break;
chkMin(F[i][j], F[i - 1][j - x.fir + 1] + x.sec);
}
chkMin(F[i][j], F[i][j - 1]);
}
}
cout << F[N][M] << endl;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
init();
int Case;
cin >> Case;
while (Case--) solve();
return 0;
}

HDU的除法极慢,不预处理出每次转移时除法的值,赛后交居然还T了。。