UVA 1204 Fun Game 状态压缩圆圈的处理

怼烎@ 2021-12-15 06:13 247阅读 0赞

## 题意：一群小孩(至少两个)围成一圈做游戏。每一轮从某个小孩开始往他左边或者右边传手帕。一个小孩拿到手帕后在手帕上写上自己的性别，男孩写B,女孩写G，然后按照相同的方向传递给下一个小孩，每一轮都可能在任何一个小孩写完后停止，现在游戏已经进行了n轮，已知n轮中每轮手帕上留下的字,问最少可能有几个小孩。 ##

## 分析：预处理去掉所有的被其他串包含的串，然后处理出所有串的重叠长度。状态的转移就很好写了嘛，考虑当前一个没有拿到的串，假设为j，正反状态为y（j要求没有拿过，即i&(1<<j)为0）,当前拿到的串的集合为s且当前最后一次的串为i,i的状态是x ##

## dp\[s|(1<<j)\]\[j\]\[y\]=dp\[s\]\[i\]\[x\]+length\[j\]-overlap\[i\]\[j\]\[x\]\[y\] ##

## length\[j\]代表第j个字符串的长度，overlap\[i\]\[j\]\[x\]\[y\]代表正反状态为x的第i字符串和正反状态为y的第j字符串的重叠长度（i左j右），最后还要处理结尾的串和起始串的重合部分，得出最终的结果。注意小孩子的个数最少为两个人。 ##

## LRJ代码： ##

#include<bits/stdc++.h>
    using namespace std;
    
    #define REP(i,n) for(int i = 0; i < (n); i++)
    
    const int maxn = 16;
    const int maxlen = 100 + 5;
    
    // the overlap length of a (left) and b (right) 求两个串的重叠长度
    int calc_overlap(const string& a, const string& b)
    {
        int n1 = a.length();
        int n2 = b.length();
        for(int i = 1; i < n1; i++)   // place b at position i (从i开始往后判断a是否与b相等)
        {
            if(n2 + i <= n1) continue; // b cannot extend to the right of a
            bool ok = true;
            for(int j = 0; i + j < n1; j++)
                if(a[i+j] != b[j])
                {
                    ok = false;
                    break;
                }
            if(ok) return n1 - i;
        }
        return 0;
    }
    
    struct Item
    {
        string s, rev;
        bool operator < (const Item& rhs) const
        {
            return s.length() < rhs.s.length();
        }
    };
    
    int n;
    string s[maxn][2];
    int len[maxn];
    int overlap[maxn][maxn][2][2];
    
    void init()
    {
        // read input
        Item tmp[maxn];
        REP(i,n)
        {
            cin >> tmp[i].s;
            tmp[i].rev = tmp[i].s;
            reverse(tmp[i].rev.begin(), tmp[i].rev.end());
        }
        // remove strings that are occurred in another string
        // 预处理，将包含于其他字符串的字串删除
        int n2 = 0;
        sort(tmp, tmp+n);
        REP(i,n)
        {
            bool need = true;
            for(int j = i+1; j < n; j++)
            {
                if(tmp[j].s.find(tmp[i].s) != string::npos ||
                        tmp[j].rev.find(tmp[i].s) != string::npos)
                {
                    need = false;
                    break;
                }
            }
            if(need) // 如果不是重复就加入数组
            {
                s[n2][0] = tmp[i].s;
                s[n2][1] = tmp[i].rev;
                len[n2] = tmp[i].s.length();
                n2++;
            }
        }
        n = n2;
        // calculate overlaps
        REP(i,n) REP(j,n) REP(x,2) REP(y,2)
        overlap[i][j][x][y] = calc_overlap(s[i][x], s[j][y]);
    }
    
    // d[s][i][x] is the minimal total length if we used set s and the last string is s[i][x]
    int d[1<<maxn][maxn][2];
    
    inline void update(int& x, int v)
    {
        if(x < 0 || v < x) x = v;
    }
    
    void solve()
    {
        // dp
        memset(d, -1, sizeof(d));
        d[1][0][0] = len[0]; // always use string s[0][0] first
        int full = (1<<n) - 1;
        for(int s = 1; s < full; s++)
        {
            // 枚举尾部
            REP(i,n) REP(x,2) if(d[s][i][x] >= 0)
                for(int j = 1; j < n; j++) // place j
                    if(!(s & (1<<j))) //枚举新加入的串
                        REP(y,2) update(d[s|(1<<j)][j][y], d[s][i][x]+len[j]-overlap[i][j][x][y]); // 更新最小值
        }
        // find answer
        int ans = -1;
        REP(i,n) REP(x,2)
        {
            if(d[full][i][x] < 0) continue;
            update(ans, d[full][i][x]-overlap[i][0][x][0]); //len[0]一开始就加过了
        }
        if(ans <= 1) ans = 2; // problem said: at least two children
        cout << ans << "\n";
    }
    
    int main()
    {
        while(cin >> n && n)
        {
            init();
            solve();
        }
        return 0;
    }