2019-2020 ACM ICPC Brazil Subregional Programming Contest E.Exhibition of Clownfish @ Wings            分类 ACM
发布于 星期六, 十二月 12 日, 2020 年
更新于 星期二, 七月 20 日, 2021 年

题目

题意

某水族馆有一种神奇的🐟, 当某一个鱼缸里没有雌鱼时, 某一条雄鱼会变成雌鱼. 水族馆里有$n$个鱼缸, 其中第$i$个鱼缸中有$a_i$条雄鱼和$b_i$条雌鱼(保证初始状态合法). 把某一个鱼缸中的一条鱼移动到另一个鱼缸需要$1$点花费. 求把所有雄鱼变成雌鱼的最小花费.

$2 \le n \le 3000, 0 \le a, b \le 10^5, a = 0 \ or\ b > 0$

题解

关键点都想出来了, 但是不太会实现, 搞了好久好久好久😭

先进行一下特判, 如果没有雄鱼, 直接输出$0$即可.

先考虑没有空缸的情况.

对一个非空鱼缸, 我们只会进行以下操作之一:

  1. 把所有雄鱼拿出来, 移动到其他缸里(可能是多个鱼缸);
  2. 把所有雌鱼拿出来, 让雄鱼依次变成雌鱼, 再一个一个拿雌鱼, 最后留一只雌鱼. 拿出来的鱼移动到其他缸里(可能是多个鱼缸).

证明简单, 略.

我们把进行第一种操作的鱼缸称为$M$, 进行第二种操作的鱼缸称为$F$.

手玩可以发现有以下性质:

  1. $M$拿出来的鱼一定会移动到某些$F$中

证明:

$M$($a_i, b_i$)拿出来的雄鱼$a_i$会放到$F$的雄鱼里, 让拿过来的雄鱼$a_i$变成雌鱼的最优方式就是这个$F$进行他的操作, 这样这$a_i$条雄鱼会被移动两次, 贡献为$2a_i$. 如果不是这样的操作, 那么只可能是把这些鱼再放到其他缸内, 这样贡献一定会大于$2a_i$, 不优. 如果是把$M$放到其他$M$里, 也会造成贡献大于$2a_i$, 不优.

所以, $M$的贡献是$2a_i$.

  1. $F$拿出来的鱼一定会移动到某些$M$中

证明:

放到$M$中, 由于$M$中的雄鱼不需要通过移动雌鱼让雄鱼变性, 所以放好以后就不用动了. 假如$F$($a_j, b_j$)拿出来的鱼$(a_i + b_j - 1)$放在某些其他$F$中, 则这些鱼还可能需要再拿出来(目标$F$有雄鱼的话), 贡献会增加, 不优.

所以, $F$的总贡献是$a_j + b_j - 1$.

由上述性质, 可以推知:

  1. 至少存在一个$M$和一个$F$才是可行的.

那么, 我们的任务就是给$n$个非空的鱼缸标号.

事实上如果题目到这里就结束了, 我们可以直接贪心解决.

但是! 这道题有空鱼缸! 加入空鱼缸之后就变得复杂多了.

空鱼缸有这些作用:

  1. 作为一个 雄鱼消除器

由前两条性质我们可以得到, 在没有空鱼缸的情况下, $M$中的一只雄鱼的贡献为$2$. 如果我们把这一条鱼移动到空鱼缸里, 贡献就是$1$了, 更优.

  1. 作为一个$M$

如果所有的非空鱼缸都是$F$的话, 可以把他们移动到空鱼缸内.

  1. 作为一个$F$

如果所有非空鱼缸都是$M$的话, 可以把他们都移动到空鱼缸内, 然后再对收集了雄鱼的空鱼缸进行$F$的操作(如果有必要).

作用$2,3$削弱了对非空鱼缸的"至少一个为$M$, 一个为$F$“的限制条件, 即可以全是$M$或者$F$.

同时, 还有这样的性质:

移动到空鱼缸里的鱼一定是某个$M$内的雄鱼

证明:

由作用1可得, 这样做可以使答案更优. $M$的雌鱼不需要移动. $F$的雄鱼或者雌鱼移动到这里, 贡献是$1$; 而原来的贡献也是$1$, 移动的话不仅不会使答案更优, 还会浪费一个可能可以减小答案的空鱼缸, 不优.

贪心一下, 当然是把尽量多的$M$中的雄鱼移动到空鱼缸中.

那么, 哪些鱼缸需要标记成$M$, 不再仅仅取决于$2a_i$与$a_i + b_i - 1$的大小关系了, 空鱼缸能对我们的选择进行影响. 所以, 贪心的方法不可行. 尝试一个能够对比两种决策(标记成$M$还是$F$)的优劣性的做法 —— DP.

一步一步来.

我们不需要给空鱼缸标号, 把他和非空鱼缸分离开, $dp$的第一维只考虑非空鱼缸.

由于空鱼缸的数量会对结果造成影响, 所以在状态中加入空鱼缸.

$dp(i, j)$表示前$i$个(非空)鱼缸, 另外有$j$个空鱼缸被使用, 即有$j$条$M$中的雄鱼被拿出来且分别放在了空鱼缸中.

如果没有空鱼缸, 鱼缸的标号是有限制条件的, 所以我们需要知道鱼缸的标号情况. 但是不需要知道具体的标号情况, 而需要知道有没有标号为$F$的和有没有标号为$M$的. 所以, 我们附加上两个状态, 分别表示前$i$个中有无$F$, $M$. 最后状态长这样:

$$dp(i, j, 0 / 1, 0 / 1)$$

表示前$i$个(非空)鱼缸中, 移动了$j$条雄鱼到$j$个空鱼缸中, 前$i$个鱼缸有/无$F$, 前$i$个鱼缸有/无$M$

$dp$方程老长老长了:

首先边界条件$dp(0, 0, 0, 0) = 0$, 其他$dp(0, 0)$的不存在, 可直接设为INF. 当$i>1$时, $dp(i, j, 0, 0)$也不存在, 设为INF.

$dp(i, j, 0, 1)$ 从以下状态转移:

$$ \begin{aligned} &dp(i-1, j, 0, 1) + 2a_i &\text{之前有M, 当前为M, 不移动到空} \newline &dp(i-1, j, 0, 0) + 2a_i &\text{之前无M, 当前为M, 不移动到空} \newline &dp(i-1, max(0, j - a_i), 0, 1) + 2 * a_i - min(j, a_i) &\text{之前有M, 当前为M, 全移动到空} \newline &dp(i-1, max(0, j - a_i), 0, 0) + 2 * a_i - min(j, a_i) &\text{之前无M, 当前为M, 全移动到空} \end{aligned} $$

$dp(i, j, 1, 0)$ 从以下状态转移:

$$ \begin{aligned} dp(i-1, j, 1, 0) + a_i + b_i - 1 \newline dp(i-1, j, 0 ,0) + a_i + b_i - 1 \end{aligned} $$

$F$中的鱼不需要移到空鱼缸, 只有这两个状态需要转移

$dp(i, j, 1, 1)$ 从以下状态转移:

$$ \begin{aligned} &dp(i-1, j, 1, 1) + 2 * a_i \newline &dp(i-1, max(0, j - a_i), 1, 1) + 2 * a_i - min(j, a_i) \newline &dp(i-1, j, 1, 1) + a_i + b_i - 1 \newline &dp(i-1, j, 1, 0) + 2 * a_i \newline &dp(i-1, max(0, j - a_i), 1, 0) + 2 * a_i - min(j, a_i) \newline &dp(i-1, j, 0, 1) + a_i + b_i - 1 \end{aligned} $$

写不动了方程不一一解释了, 代码注释里有写.

最后, 取答案需要分情况讨论:

没有空鱼缸, 那么必须满足"至少一个$M$, 一个$F$“的条件, 所以答案是$dp(non\_empty, 0, 1, 1)$

有空鱼缸, 没有限制条件. 枚举空鱼缸的使用数量, 对$dp(non\_empty, k, 0/1, 0/1), 0 \le k \le empty\_tank$ 取min就是答案了.

复杂度$O(n^2)$

终于写完了…

总结一下, 为什么没有想到这样的dp

首先, 没有想到只需要保存"前$i$个是否有标号为$M$或$F$“这样的状态, 傻乎乎地保存前$i$个有$j$个标号为$M$.

其次, 没有想到把空鱼缸数量保存在状态里. 可能是受到保存了$M$的个数的影响, 再加一维就炸了, 所以根本没往这方面想.

代码

由于一开始开了LL, 然后炸空间了, 所以$dp$滚了第一维. 后来发现最大值不会超过int, 于是改回了int, 但是滚动数组依然保留, 没算不滚会不会炸.

const int MAXN = 3e3+10;

int n, empty_tank, non_empty_tank, a[MAXN], b[MAXN];
int dp[2][MAXN][2][2], male = 0;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		if (!x && !y)
			empty_tank++;
		else {
			a[++non_empty_tank] = x;
			male += x;
			b[non_empty_tank] = y;
		}
	}
	if (!male) {
		puts("0");
		return 0;
	}

	for (int i = 0; i <= empty_tank; i++) {
		dp[0][i][0][0] = dp[0][i][0][1] = dp[0][i][1][0] = dp[0][i][1][1] = INTINF;
		dp[1][i][0][0] = dp[1][i][0][1] = dp[1][i][1][0] = dp[1][i][1][1] = INTINF;
	}
	dp[0][0][0][0] = 0;
	for (int i = 1; i <= non_empty_tank; i++) {
		for (int j = 0; j <= empty_tank; j++) {
			//至少有一个是F或者M, 所以00不存在.
			int cur = i&1;
			// 初始化
			dp[cur][j][0][0] = dp[cur][j][0][1] = dp[cur][j][1][0] = dp[cur][j][1][1] = INTINF;

			dp[cur][j][0][0] = INTINF;

			int &dpij01 = dp[cur][j][0][1];
			// 之前有M, 当前为M, 不移动到空
			dpij01 = min(dpij01, dp[cur^1][j][0][1] + 2 * a[i]);
			// 之前无M, 当前为M, 不移动到空
			dpij01 = min(dpij01, dp[cur^1][j][0][0] + 2 * a[i]);
			// 之前有M, 当前为M, 全移动到空
			// 如果这个a为0, 那么下面第一个方程无法按照"把0放到空"这样的表达方式进行转移, 特判一下
			dpij01 = min(dpij01, dp[cur^1][max(0, j - a[i])][0][1] + 2 * a[i] - min(j, a[i]));
			// 之前无M, 当前为M, 全部移到空
			dpij01 = min(dpij01, dp[cur^1][max(0, j - a[i])][0][0] + 2 * a[i] - min(j, a[i]));

			int &dpij10 = dp[cur][j][1][0];
			// 由于F移动到空和不移动到空的花费相同, 移动的话浪费了空, 不划算, 所以F不移动到空
			// 之前有F, 当前为F
			dpij10 = min(dpij10, dp[cur^1][j][1][0] + a[i] + b[i] - 1);
			// 之前无F, 当前为F
			dpij10 = min(dpij10, dp[cur^1][j][0][0] + a[i] + b[i] - 1);

			int &dpij11 = dp[cur][j][1][1];
			// 之前有F和M, 当前为M, 不移动到空
			dpij11 = min(dpij11, dp[cur^1][j][1][1] + 2 * a[i]);
			// 之前有F和M, 当前为M, 全移动到空
			dpij11 = min(dpij11, dp[cur^1][max(0, j - a[i])][1][1] + 2 * a[i] - min(j, a[i]));
			// 之前有F和M, 当前为F, 不移动到空
			dpij11 = min(dpij11, dp[cur^1][j][1][1] + a[i] + b[i] - 1);
			// 之前有F无M, 当前为M, 不移动到空
			dpij11 = min(dpij11, dp[cur^1][j][1][0] + 2 * a[i]);
			// 之前有F无M, 当前为M, 全移动到空
			dpij11 = min(dpij11, dp[cur^1][max(0, j - a[i])][1][0] + 2 * a[i] - min(j, a[i]));
			// 之前无F有M, 当前为F, 不移动到空
			dpij11 = min(dpij11, dp[cur^1][j][0][1] + a[i] + b[i] - 1);
		}
	}

	int ans = INTINF;
	if (empty_tank)
		for (int i = 0; i <= empty_tank; i++) {
			ans = min(ans, dp[non_empty_tank&1][i][0][0]);
			ans = min(ans, dp[non_empty_tank&1][i][1][0]);
			ans = min(ans, dp[non_empty_tank&1][i][0][1]);
			ans = min(ans, dp[non_empty_tank&1][i][1][1]);
		}
	else
		ans = dp[non_empty_tank&1][0][1][1];
	printf("%d\n", ans);
	return 0;
}
留下昵称和邮箱, 可在第一时间获悉回复通知哦~

2021 FLAG

  • 找个妹子
  • 进计科
  • XCPC拿块金牌
  • 补全算法知识, 整全板子
  • 学会Web开发相关知识
  • 在服务器上搭建电子书库
  • 写个游戏并上线
  • 能弹一首曲子
  • 写首完整的曲子
  • 练习悠悠球

个人简介

我叫 Wings, 来自江西上饶, 目前人在西安, 是西电的一名学生.

常以 WingsWingsZengWingsWings的ID在各大小网站上游走, 一般来说, Wings不是我 😔, WingsZeng 一定是我 😊.

热爱算法, 喜欢钻研各种计算机技术.

业余爱好广泛, 只要不是文化课基本上都感兴趣😏.

开发/项目经历

  1. Android游戏 小墨滴的复仇 (弃坑)
  2. Android游戏 Circle Run (弃坑)
  3. Windows游戏 Snague (可能弃坑了吧)
  4. Python后端 Fathy' (可能弃坑了吧)

to be continued

教育经历

时间 学历 学校
2008-2014 小学 上饶市第十二小学
2014-2017 初中 上饶市第四中学
2017-2020 高中 上饶市第一中学
2020-2024 本科 西安电子科技大学
to be continued

比赛/竞赛经历

太久远太小的记不到了…

  1. 2017 国学竞赛初赛江西 没有分数或排名 二乙
  2. 2018 NOIP提高 258 省二
  3. 2019 CSP-S江西专场 145 省二
  4. 2019 数学竞赛初赛 70 没排名 (复赛打铁qaq)
  5. 2020 Gitee|Python贪吃蛇魔改大赛 可能是第四? 二等奖
  6. 2020 西电ACM训练基地熊猫杯 第四 银牌
  7. 2020 西安三校微软学生俱乐部Hackathon 和二等奖最后一名差0.5分 三等奖
  8. 2020 西电星火杯 三等奖
  9. 2020 西电ACM新生赛 第九 金牌
  10. 2020 ICPC 亚洲区域赛 济南站 132名 铜牌
  11. 2020-2021 第二届全国大学生算法设计与编程挑战赛(冬季赛) 924名 铜牌 (别骂了别骂了)
  12. 2020 ICPC 亚洲区域赛 昆明站 打星
  13. 2020 ICPC Asia-East Continent Final 签完到溜 打铁
  14. 西电"智能星"第一届自动驾驶小车比赛 第五 优胜奖|极速奖 本来可以冠军的别骂了别骂了
  15. 2021团体程序设计天体赛(CCCC) 个人二等奖
  16. 2021 西电 miniL CTF 优胜奖
  17. 2021 西电ACM校赛 第9名 金牌
  18. 2021 西电数模校赛 二等奖
  19. 2021 第15届IEEE 第48名
  20. 2021 CCPC 桂林站 打星

to be continued

爱好

技术

  • 算法
  • 独立游戏开发

游戏

  • Minecraft
  • Black Survival
  • I Wanna
  • Celeste
  • Life is Strange
  • Need for speed

运动

  • 篮球
  • 桌球
  • 乒乓球
  • 羽毛球
  • 慢跑

音乐

  • 吉他
  • 词曲
  • 流行

玩具

  • 魔方
    • 三阶速拧
    • 三阶盲拧
    • 高阶
  • yoyo球

追星

  • VAE
  • Benedict Cumberbatch