[POI2010]CHO-Hamsters
# include
# include
# include
# include
# include
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
IL ll Read(){
RG char c = getchar(); RG ll x = 0, z = 1;
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';
return x * z;
}
int n, m, nxt[210][100010], len[210];
char s[210][100010];
struct Matrix{
ll a[210][210];
IL void Clear(){ Fill(a, 63); }
IL ll* operator [](RG int x){ return a[x]; }
IL Matrix operator *(RG Matrix &B){
RG Matrix C; C.Clear();
for(RG int i = 0; i <= n; i++)
for(RG int j = 0; j <= n; j++)
for(RG int k = 0; k <= n; k++)
C[i][k] = min(C[i][k], a[i][j] + B[j][k]);
return C;
}
} ans, edge;
int main(RG int argc, RG char* argv[]){
edge.Clear(); ans.Clear();
n = Read(); m = Read();
for(RG int i = 1; i <= n; i++)
scanf(" %s", s[i] + 1), len[i] = strlen(s[i] + 1);
for(RG int k = 1; k <= n; k++)
for(RG int i = 2, j = 0; i <= len[k]; i++){
while(j && s[k][j + 1] != s[k][i]) j = nxt[k][j];
if(s[k][j + 1] == s[k][i]) j++;
nxt[k][i] = j;
}
for(RG int x = 1; x <= n; x++){
edge[0][x] = len[x];
for(RG int y = 1; y <= n; y++)
for(RG int i = 2, j = 0; i <= len[x]; i++){
while(j && s[y][j + 1] != s[x][i]) j = nxt[y][j];
if(s[y][j + 1] == s[x][i]) j++;
if(i == len[x]) edge[x][y] = len[y] - j;
}
}
for(RG int i = 0; i <= n; i++) ans[i][i] = 0;
for(; m; m >>= 1, edge = edge * edge) if(m & 1) ans = ans * edge;
RG ll min_len = 1e18;
for(RG int i = 1; i <= n; i++) min_len = min(ans[0][i], min_len);
printf("%lld
", min_len);
return 0;
}
전재 대상:https://www.cnblogs.com/cjoieryl/p/8206388.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.