OI - RGB Balls(AtCoder)

思路倒是挺不错
找到了一道比较奇怪的利用了“费用提前计算”方法的题目


Part1. 题面

有 3 种球,分别标记为 R,G,B。每种球各有 n 个,这 3n 个球排成一行。

现在将这 3n 个球分成 n 组,使得每一组中每种球恰有一个。每个分组的代价为该组球中相隔最远的两个球的距离。

问有多少种不同的分组方式,使得分组的总代价最小(两种方式被考虑为不同当且仅当至少有一个组中有不同的球)。

数据规模:$1\le n\le10^5$。


Part2. 题解

Part2/1. 怎样计算最小值

要知道最小值的方案数,首先要知道最小值怎么算。不妨考虑一种非常暴力的 DP:dp[i][a][b][c][d][e][f] 表示:前 i 个球中,3 种球各有 a,b,c 个没有配对(已经被分到组中的球就叫“已配对”),(R,G) 配对了 d 对,(R,B) 配对了 e 对,(G,B) 配对了 f 对。

但是我们发现这样似乎不能转移,因为我们不知道未配对的球的位置,也就无法计算距离。其实是可以转移的,这里就要用到“费用提前计算”了,转移分为三种(不妨设当前考虑的球为 R,对应的数量是 a;其他两种情况是一样的):

  1. 不配对:

    dp[i][a+1][b][c][d][e][f]=dp[i-1][a][b][c][d][e][f]+(a+b+c+d+e+f)

    后面的 a+b+c+d+e+f 就是费用提前计算了——这已经存在的 a+b+c 个球和 d+e+f 对球仍未完成分组,必然会增加 1 的花费。

  2. 与 G 配对:

    dp[i][a][b-1][c][d+1][e][f]=dp[i-1][a][b][c][d][e][f]+(a+b+c+d+e+f)

    与 B 配对是类似的。

  3. 与一对 (G,B) 配对:

    dp[i][a][b][c][d][e][f-1]=dp[i-1][a][b][c][d][e][f]+(a+b+c+d+e+f)

以上只是帮助理解贪心的正确性,代码实现中并不会体现这一段——不难发现,我们要 让 a+b+c+d+e+f 尽可能小 才可能使 dp 值更优。因此,当我们拿到一个 R 球,如果有一对未配对的 G,B 球,一定会配对成一组;如果有单个未配对的 G 或 B,一定会与它组成一对,即固定为分在同一组中。

Part2/2. 贪心

于是就有了一个非常easy的贪心:记录 3 种球在之前有多少个未完成分组,显然不会同时有 3 种球未完成分组。

考虑当前这个球,如果能够和之前未配对的球配对,那就配对了。又因为推导这个贪心结论时,我们是利用动态规划的“费用提前计算”,所以当前的球具体与前面的哪两个球配对并不重要,因此组合数算一算即可。

如果无法配对,那就更改未配对的球的数量。

这样扫一遍 $O(n)$,可以 AC 了。(其实难点在证明这个贪心是正确的)


Part3. 源代码

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5,MOD=998244353;

int n;
char str[3*N+3];

struct MODNUM{
int num;
MODNUM(){}
MODNUM(int _n):num(_n){}
MODNUM operator *(const MODNUM B){return 1ll*num*B.num%MOD;}
MODNUM operator +(const MODNUM B){return (1ll*num+B.num)%MOD;}
MODNUM operator -(const MODNUM B){return ((1ll*num-B.num)%MOD+MOD)%MOD;}
MODNUM operator +=(const MODNUM B){return *this=(*this)+B;}
MODNUM operator *=(const MODNUM B){return *this=(*this)*B;}
MODNUM operator -=(const MODNUM B){return *this=(*this)-B;}
}ans,num[4][4];

int main(){
// freopen("legend.in","r",stdin);
// freopen("legend.out","w",stdout);
scanf("%d%s",&n,str+1);
for(int i=1;i<=3*n;i++){
if(str[i]=='R') str[i]='1';
if(str[i]=='G') str[i]='2';
if(str[i]=='B') str[i]='3';
}
ans=1;
for(int i=1;i<=3*n;i++){
int ano1,ano2,thi=str[i]-'0';
if(str[i]=='1') ano1=2,ano2=3;
if(str[i]=='2') ano1=1,ano2=3;
if(str[i]=='3') ano1=1,ano2=2;
if(num[ano1][ano2].num) ans*=num[ano1][ano2],num[ano1][ano2]-=1;
else if(num[ano1][0].num) ans*=num[ano1][0],num[ano1][0]-=1,num[min(ano1,thi)][max(ano1,thi)]+=1;
else if(num[ano2][0].num) ans*=num[ano2][0],num[ano2][0]-=1,num[min(ano2,thi)][max(ano2,thi)]+=1;
else num[thi][0]+=1;
}
for(int i=1;i<=n;i++) ans*=i;
printf("%d\n",ans);
return 0;
}

The End

Thanks for reading!

啊哈?又完成一篇 blog 了呢!

0%