题面

题目链接

https://ac.nowcoder.com/acm/contest/5633/D

题目大意

n 颗宝石装进 n 个箱子使得 , 每个箱子中都有一颗宝石

其中第 i 颗宝石不能装入第 ai 个箱子 , 求合法的装箱方案数。

解题思路

总的装箱方案为 N! ，答案 = 总方案数 - $\sum ^{n}_{i=0}f\left( i\right) $ , 其中 f(x) 表示 x 个箱子不合法的方案数

我们定义 dp[i][j] 表示前 i 个箱子有 j 个放了不合法的宝石其他 i - j 个箱子不放宝石的方案数

那么 $dp_{ij}=dp_{i-1j}+dp_{i-1j-1}\times a_{i}$ , 前 n 个箱子至少有 i 个不合法的方案数为 $dp_{ni}\times \left( n-i\right) !$

AC_Code

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
string s[N] ;
int nex[N];
void get_nex(string s , int *nex)
{
    int i = 0 , j = -1 , len = s.size();
    nex[i] = j;
    while(i < len)
    {
        while(j != -1 && s[i] != s[j]) j = nex[j];
        nex[++ i] = ++ j ;
    }
}
int KMP(string s , string t)
{
    get_nex(t , nex) ; 
    int i = 0 , j = 0 , lens = s.size() , lent = t.size();    
    while(i < lens)
    {
        while(j != -1 && s[i] != t[j]) j = nex[j];
        i ++ , j ++ ;
        if(j == lent) return lent;
    }
    return j;
}
int solve(string a , string b , string c)
{
    int pos = KMP(a , b);
    a += b.substr(pos , b.size() - pos);
    pos = KMP(a , c);
    return a.size() + c.size() - pos;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin >> s[1] >> s[2] >> s[3];
    sort(s + 1 , s + 1 + 3);
    int ans = s[1].size() + s[2].size() + s[3].size();
    do{
        ans = min(ans , solve(s[1] , s[2] , s[3]));
    }while(next_permutation(s + 1 , s + 1 + 3));
    cout << ans << '\n' ;
    return 0;
}