一眼區間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...