水题笔记_ vijos1240 朴素的网络游戏 [清奇脑回路] [DP]

观察出一些不起眼的结论可以让题目瞬间可做

懵逼的 题目

传送至 Vijos

扯淡的 题解

终于回来了, 期中考试爆炸了, 终于知道以前保皇为啥没有炸了….
最近打算练一下DP(flag?)

一开始只能想到4维的DP
然后看了题解(果然文化课的进步和竞赛的退步是成指数函数的…)知道了:

最终的安排最多只有1对夫妇住在一个房间, 因为如果有两对夫妇在一个房间, 就可以把男方和男方放在一个房间 女方和女方放在一个房间, 这样答案不会更差

然后就解决了, 记f[i][j][k][1 / 0]为当前在分配第i个房间, 还剩下j个女生和k个男生要分配, 当前有 / 没有把一对夫妇分在一个房间
然后我用刷表写完
WAWAWAWA

今天才发现是没有注意分配一对夫妇给一个房间的时候没有判断这个房间是不是容积比2大…GG

沙茶的 代码

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
78
79
80
// 注意到整个安排中最多只会有一对夫妻同房, 否则可以两男两女分开住
// 然后就比较简单了

#include <cstdio>
#include <cstring>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define MAXN (300 + 5)
#define MAXM (300 + 5)
#define MAXF (300 + 5)
#define INF (0x7ffffff)
#define yd(x) ((x >= 0) ? (x) : (0))
struct room
{
int v;
int c;
}a[MAXN];
int n;
int nm;
int nf;
int nc;
int f[MAXN][MAXM][MAXF][2];// f[i][j][k][0 / 1]: 当前在给第 i 个房间安排, 还剩下 j 个男的和 k 个女的, 没有 / 有夫妇入住 的最小花费
int ans;
void solve();
int main()
{
memset(f, 0x7f, sizeof(f));
// std::cout << "Hello, World!" << std::endl;
scanf("%d%d%d%d", &nm, &nf, &n, &nc);
for (int i = 1; i <= n; i++)
{
scanf("%d%d", &a[i].v, &a[i].c);
}
solve();
if (ans < INF)
printf("%d", ans);
else
puts("Impossible");
return 0;
}
void solve()
{
f[1][nm][nf][0] = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= nm; j++)
{
for (int k = 0; k <= nf; k++)
{
f[i + 1][j][k][1] = min(f[i + 1][j][k][1], f[i][j][k][1]);

f[i + 1][j][yd(k - a[i].v)][1] = min(f[i][j][k][1] + a[i].c, f[i + 1][j][yd(k - a[i].v)][1]);
f[i + 1][yd(j - a[i].v)][k][1] = min(f[i][j][k][1] + a[i].c, f[i + 1][yd(j - a[i].v)][k][1]);

//------------------------------------------------------------------------------------------------------

f[i + 1][j][k][0] = min(f[i + 1][j][k][0], f[i][j][k][0]);

if (j > 0 && k > 0 && nc > 0 && a[i].v >= 2)
f[i + 1][yd(j - 1)][yd(k - 1)][1] = min(f[i][j][k][0] + a[i].c, f[i + 1][yd(j - 1)][yd(k - 1)][1]);

f[i + 1][j][yd(k - a[i].v)][0] = min(f[i][j][k][0] + a[i].c, f[i + 1][j][yd(k - a[i].v)][0]);
f[i + 1][yd(j - a[i].v)][k][0] = min(f[i][j][k][0] + a[i].c, f[i + 1][yd(j - a[i].v)][k][0]);
}
}
}
ans = min((nc > 0 ? f[n + 1][0][0][1] : INF), f[n + 1][0][0][0]);
}

/*
2 1 3 1
3 5
2 10
2 4
*/

/*
1 1 1 0
1 4
*/

By 期中炸飞的 Cansult

%%% AH