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

題目大意

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

題解

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

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

dp[S]={0if S=∅min{dp[S−{i,j,k}]+v[i][j]+v[j][k]+v[k][i]}otherwise

其中 i,j,k∈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';
    }
}