SCOI2003 字串摺疊

2022-11-27 15:07:42 字數 801 閱讀 7318

一眼區間dp。

設\(f[i][j]\)表示:將區間\([i,j]\)內的所有東西壓一起的最短長度。

顯然,有兩種方法:

1.在中間一刀劈開,然後拼一起。

2.找到它的迴圈節,然後把整個串壓一起。

至於找迴圈節嗎……列舉迴圈節長度,然後無腦雜湊一下。

注意,你可能會壓出類似於\(10(ab)\)這種東西,記得\(10\)是兩位數!!!

**:

#includeusing namespace std;

typedef unsigned long long ull;

char s[110];

int n,f[110][110];

ull sd1=998244353,sd2=666623333,pov1[2001000],pov2[2001000];

struct hash

hash(char ip)

friend hash operator +(const hash &x,const hash &y)

friend hash operator -(const hash &x,const hash &y)

friend bool operator ==(const hash &x,const hash &y)

}hs[110];

int calc(int x)

int main()

} }// for(int i=1;i<=n;i++)

printf("%d\n",f[1][n]);

return 0;

}

P4302 SCOI2003 字串摺疊

我居然在第一個最優解?設 f 為 i,j 中的最短長度。得 f min min limits f min limits len l 2 其中 len x 為 x 的位數,l 為迴圈節數。時間複雜度 o n 4 顯然不是。在 s i,k 的長度不整除 s i,j 的長度時,顯然不成立,剪枝。inclu...

BZOJ1090 SCOI2003 字串摺疊

試題描述 摺疊的定義如下 一個字串可以看成它自身的摺疊。記作 s rightarrow s x s 是 x x 1 個 s 連線在一起的串的摺疊。記作 x s rightarrow ssss s x個s 如果 a rightarrow a b rightarrow b 則 ab rightarrow...

BZOJ1089 SCOI2003 嚴格n元樹

求出深度為d的嚴格n元樹的個數 hanks o f i 表示深度小於等於i的嚴格n元樹。那麼f i 怎麼用f i 1 表示呢。對於任意一個深度為i的嚴格n元樹。那麼它的根一定有n個兒子。這樣我們就可以把它拆成一個根和n棵深度小於等於i 1的n元樹了。那麼深度小於等於i 1的n元樹方案已經求出來了是f...