目录
- 第二题
- 题目描述
- 输入描述
- 输出描述
- 分析
- 第三题
- 题目描述
- 输入描述
- 输出描述
- 例子
- 分析
第二题
题目描述
小v是公司的运维工程师，现有一个有关应用程序部署的任务如下：
1、一台服务器的磁盘空间、内存是固定的，现在有N个应用程序要部署；
2、每个应用程序所需要的磁盘、内存不同，每个应用程序允许访问的用户数也不同，且同一个应用程序不能在一台服务器上部署多个。
对于一台服务器而言，如何组合部署应用程序能够使得单台服务器允许访问的用户数最多？
输入描述
输入包括三个参数，空格分隔，分别表示服务器的磁盘大小、内存大小，以及应用程序列表；
其中第三个参数即应用程序列表，表述方式为：多个应用程序信息之间用‘#’分隔，每个应用程序的信息包括‘,’分隔的部署所需磁盘空间、内存、允许访问的用户量三个数字；
比如50,20,2000 表示部署该应用程序需要50G磁盘空间，20G内存，允许访问的用户数为2000
输出描述
分析
- 二维的0-1背包问题
- dp[N][D][M]表示在有N个APP，磁盘大小为D、内存大小为M的条件下，最多能有多少访问量。
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
| int helper(const int disk, const int memory, vector<int>& disks, vector<int>& memories, vector<int>&visitors) {
const int N = disks.size();
vector<vector<vector<int> > > dp(N + 1, vector<vector<int> >(disk + 1,
vector<int>(memory + 1, 0)));
for (int i = 1; i <= N; ++i) {
for (int d = 1; d <= disk; ++d) {
for (int m = 1; m <= memory; ++m) {
if (m >= memories[i - 1] && d >= disks[i - 1]) {
int t1 = dp[i - 1][d - disks[i - 1]][m - memories[i - 1]] + visitors[i - 1];
int t2 = dp[i - 1][d][m];
dp[i][d][m] = t1 > t2 ? t1 : t2;
}
else
dp[i][d][m] = dp[i - 1][d][m];
}
}
}
return dp[N][disk][memory];
}
int main() {
int disk, memory;
cin >> disk >> memory;
string s;
cin >> s;
vector<int> disks, memories, visitors;
for (int i = 0; i < s.size(); ++i) {
string t = "";
while (i < s.size() && s[i] != '#')
t += s[i++];
vector<string> vec;
for (int j = 0; j < t.size(); ++j) {
string t2 = "";
while (j < t.size() && t[i] != ',')
t2 += t[j++];
vec.push_back(t2);
}
int n;
stringstream ss;
for (int i = 0; i < 3; ++i) {
ss << vec[0];
ss >> n;
if (i == 0) disks.push_back(n);
else if (i == 1) memories.push_back(n);
else visitors.push_back(n);
}
}
cout << helper(disk, memory, disks, memories, visitors) << endl;
return 0;
}
|
第三题
题目描述
一维开心消消乐，每次消除得分为消除个数k的平方，k>=1。
输入描述
输入一行n个正整数，代表这一行中豆子的颜色及排列。
输出描述
例子
- 输入：1 4 2 2 3 3 2 4 1
- 输出：21
分析
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
| int main() {
int t;
vector<int> boxes;
while (cin.get() != '\n') {
cin >> t;
boxes.push_back(t);
}
const int n = boxes.size();
int dp[n][n][n] = {0};
for (int i = 0; i < n; ++i) {
for (int k = 0; k <= i; ++k) {
dp[i][i][k] = (1 + k) * (1 + k);
}
}
for (int t = 1; t < n; ++t) {
for (int j = t; j < n; ++j) {
int i = j - t;
for (int k = 0; k <= i; ++k) {
int res = (1 + k) * (1 + k) + dp[i + 1][j][0];
for (int m = i + 1; m <= j; ++m) {
if (boxes[m] == boxes[i])
res = max(res, dp[i + 1][m - 1][0] + dp[m][j][k + 1]);
}
dp[i][j][k] = res;
}
}
}
cout << n == 0 ? 0 : dp[0][n - 1][0] << endl;
return 0;
}
|
