尝试使用了EOJ 双塔问题的思路进行DP，质量可以类比塔的高度，然而忽略了双塔问题中要求让两个塔高度相同时候求高度的最大值，本题中二者质量可能不同。
思路
对比
- 传统的０／１背包问题：给定物品的重量和价值，一个有限制的背包，目标是让背包中装入物品价值总和最大
- 本题（饼干分配问题）：给定两个背包，没有明确限制，要求最后分组让两个背包差值最小
联系
- 饼干对应背包中的物品，饼干质量对应物品重量。虽然没有给出背包的容积但可以任务让每个背包中重量接近总重量的一半。
- 定义$dp[i][j]$前$i$个物品放入质量为$j$ 的背包的最大重量（本题中$j$为总质量的一般）
- 状态转移方程$dp[i][j]=dp[i-1][j]$(不选第$i$个饼干) or $dp[i][j]=dp[i-1][j-w[i]]+w[i]$(选择第$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
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10, M = 30;
int w[M];
int f[M][N];
int n, m;
int main()
{
while(cin >> n)
{
memset(f, 0, sizeof f);
m = 0;
for(int i = 1; i <= n; i ++) {
scanf("%d", &w[i]);
m += w[i];
}
for(int i = 1; i <= n; i ++)
for(int j = 0; j <= m / 2; j ++)
{
f[i][j] = f[i - 1][j];
if(j >= w[i])
f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + w[i]);
}
int ans = m - 2 * f[n][m / 2];
cout << ans << endl;
}
return 0;
}
|
思路
一道数学公式推到。设$f(n)为n的不同拆分方案数$，有递推式
$$
f(2m + 1) = f(2m),f(2m) = f(2m - 1) + f(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
| #include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
const int N = 10010;
int is_firm(int num, int div)
{
if(num < div)
return num;
else if(num % div == 0)
return 0;
else
return is_firm(num - num / div, div + 1);
}
int main()
{
int T;
cin >> T;
for(int q = 0; q < T; q ++)
{
int n;
cin >> n;
printf("case #%d:\n", q);
int pos = is_firm(n, 2);
if(pos)
cout << "Yes " << pos << endl;
else
cout << "No" << endl;
}
return 0;
}
|
思路
在板子上模拟后发现第$i$轮之后数组中的前$i$个数字都是安全的，换句话说不会在之后被筛掉。开一个$st[N]$数组来记录哪些数字已经被筛掉。这会有两个问题
时间复杂度过高
边界情况考虑不全
在评论区翻到一位大佬的回答豁然开朗，使用了类似dfs的思想，太天才了。
代码
详见评论区
思路
占位，只考虑了贪心问题，没考虑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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N];
int n, k, p;
int m[6] = {100, 50, 20,10, 5, 1};
int get_max_ticket(int x)
{
int res = 0;
for(int i = 0; i < 6; i ++)
{
if(x == 0) break;
if(x < m[i]) continue;
res += x / m[i];
x %= m[i];
}
return res;
}
int main()
{
memset(f, 0x3f, sizeof f);
cin >> n >> k >> p;
f[0] = 0;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= i && j <= k; j ++)
{
f[i] = min(f[i], f[i - j] + get_max_ticket(j * p));
}
cout << f[n] << endl;
return 0;
}
|
占位，线性筛+二分???
