$$\newcommand{\Ord}{\mathcal{O}}$$

1418. 交大都是雷

連結:https://tioj.ck.tp.edu.tw/problems/1418

題目大意

有$N$位同學要每三個人湊成一組,每湊成一組可以計算出一個雷度,問要怎麼湊才能使整體雷度最低。

題解

這題目名稱感覺挺容易起爭議的,而且這題時限我覺得設計的很差,只有特定的實作才能過最後一筆。

如果不記最後一筆,可以很簡單的用位元DP處裡掉,因為可以任選三人,DP時因此可以固定先選一人,再任選兩人,讓枚舉的複雜度變低,可以再$O(N^2 2^N)$的時間完成。

$$dp[S]=\begin{cases}0 & \text{if }S=\emptyset \\ \min\{dp[S-\{i,j,k\}]+v[i][j]+v[j][k]+v[k][i]\}&\text{otherwise}\end{cases}$$

其中 $i,j,k\in S$

要過最後一筆,我試過先提出可以用行的數字放在新的陣列中處裡,不過這樣反而讓其他的優化處理變差。然後參考網路上有的實作,DP變成向後更新數字,然後就過了,我覺得很莫名。約有4倍的速度差,我個人認為是這樣處裡能留下的快取比向前的還要來的多,不過一般出題卡這種細節我覺得不太行。

AC Code

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
#include<bits/stdc++.h>
using namespace std;
int dp[1<<21];
int R[21][21];

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);

int T,N;
cin>>T;

while(T--)
{
cin>>N;
for(int i=0;i<N;++i)
for(int j=0;j<N;++j)
cin>>R[i][j];

int ans = (1<<N)-1;
#define test_bit(a,b) ((a)&(1<<(b)))
#define pw(a) (1<<(a))
#define pr(i,j,k) (pw(i)|pw(j)|pw(k))
int i,j,k;
memset(dp, 0x3f, sizeof(int)*(1+ans));
dp[0]=0;
for(int v=0;v<ans;++v)
{
if(dp[v]==0x3f3f3f3f)continue;
i=__builtin_ctz(~v);

for(j=i+1;j<N;++j)
if( !test_bit(v,j) )
{
for(k=j+1;k<N;++k)
if( !test_bit(v,k) )
if( dp[v|pr(i,j,k)] > dp[v]+R[i][j]+R[j][k]+R[k][i] )
dp[v|pr(i,j,k)] = dp[v]+R[i][j]+R[j][k]+R[k][i];
}
}
cout<<dp[ans]<<'\n';
}
}