题意
直线上有 $n$ 个箱子，第 $i$ 个箱子是 R 或者 B 中的一种。R 的箱子高度是 $1$，B 的箱子高度是 $\sqrt 2$。
现在你可以进行若干次操作，每次选择两个不交区间 $[l_1,r_1],[l_2,r_2]$，满足：
- $r_1-l_1 = r_2-l_2$
- $[l_2,r_2]$ 所有箱子的高度都相同
并且将 $[l_1,r_1]$ 的箱子堆到 $[l_2,r_2]$ 上面。堆完之后会改变 $[l_2,r_2]$ 的箱子的高度，然后将 $[l_1,r_1]$ 位置删除，并重标号剩下的箱子。
要求在删除过程中一直保证只有不超过 $2$ 种高度出现，求最小操作次数把所有箱子堆在一起。
$n \leq 300$。
题解
神仙题。
考虑给出 $1,\sqrt 2$ 这两个数字是干啥的。这其实是说，我们可以用向量 $(x,y)$ 表示高度 $x+\sqrt 2 y$。这样两个高度相同当且仅当向量相同。
一开始我们有的高度只有 $(0,1)$ 和 $(1,0)$。感性理解好像移动之后新的局面可以抽象成一开始的局面。其实我们就是要证明：在最优解的限制下，高度一定线性无关。
如果现在有两个高度 $\vec a,\vec b$，操作后第一种情况是变成了 $\vec a,\vec a + \vec b$，这显然还是线性无关的。
第二种情况是变成了只有 $\vec a+\vec b$，这时候就有可能裂出两个线性相关的变量（比如 $6$ 个 $\vec x$ 裂成 $2$ 个 $2\vec x$ 和 $2$ 个 $\vec x$），所以我们需要特殊处理一下只有一种高度的情况。
只有一种高度的情况，我们一定会贪心的尽量匹配所有的段。也就是说，可能会搞出两个线性相关的向量，但是一定其中一个向量只有 $1$ 个，所以不会存在一个向量能表出另一个的情况。还可以假设这个还是线性无关的。
认为他是线性无关的，我们可以把两种高度分别命名为 R 和 B，然后用 RB 序列替换。进一步发现序列只需要记录连续段长度，比如可以把 RRBRRBBRRR 压缩成 21223。记 R 代表的高度为 $x$，B 代表的高度为 $y$，分类讨论一下操作有哪几类：
1. 选择的区间同时有 R 和 B
那么我们把这个区间接在新区间上之后，设新区间颜色是 R，一定会产生新高度 $x+x$ 和 $x+y$。那么如果有的位置没有被这两个区间选中，就一定会出现至少三个高度，就不合法了。所以我们选的一定恰好是一个长度为一半的前缀。
我们先判断长度和是否是偶数，如果是，判断第一个/最后一个连续段是否占了超过一半，如果都满足的话就可以把另一半加到这一半上继续递归。
2. 选择的区间是一种颜色
设 $n$ 是连续段数量。
如果 $n \geq 6$，连续段形如 RBRBRB...（这里一个字母代表一段这样的连续段，下同），操作谁都不可能消去和自己一样的全部的位置，所以是不可能的。
如果 $n=5$，连续段形如 RBRBR，第 $2$ 个和第 $4$ 个 B 如果长度相同可以相互搬过去。
如果 $n=4$，连续段形如 RBRB，可以考虑第 $1$ 个和第 $3$ 个 R，也可以考虑第 $2$ 个和第 $4$ 个 B。
如果 $n \leq 3$，情况稍微有点多，等到后面再说。
观察一下，如果 $n \geq 6$，每次只有一种操作可能，如果 $3 < n < 6$，每次操作必定会让 $n$ 减少，所以暴搜到达 $n \leq 3$ 的状态只有常数个。而 $n \leq 3$ 的状态只有 $O(sm^3)$ 个。可以恰好开个数组记录一下。这一部分复杂度是 $O(300^3)$ 的。所以复杂度应该是一个 $300^3$ 乘上一个小常数。并且这个 $300^3$ 本身就十分不满，所以可以过。
3. 关于剩下的情况
如果 $n=3$ 的时候，连续段形如 RBR，可以：
- 第 $1$ 个
R和第 $3$ 个R长度相等，互相覆盖 - 第 $2$ 个
B长度是偶数，内部自己覆盖自己 B和某个R的长度相等，互相覆盖B去覆盖某个长度比它长的R段的边界，组成一部分是 $x+y$，一部分是 $x$ 的情况。这种情况要求B的长度不是最大的
如果 $n=2$ 的时候，连续段形如 RB，可以：
R长度是偶数，内部覆盖B长度是偶数，内部覆盖R和B长度相等，直接覆盖RB中短的去覆盖长的，造出 $x+y$ 和 $x$ 或 $y$。
如果 $n=1$ 的时候，根据上面的方法贪心覆盖就好了。
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define DB double
#define U unsigned
#define P std::pair
#define LL long long
#define LD long double
#define pb emplace_back
#define MP std::make_pair
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
class ForkliftTruckOperator{
public:
int f[305][305][305];
inline int& calc(std::vector<int> vec){
assert(SZ(vec) <= 3);
while(SZ(vec) != 3) vec.pb(0);
return f[vec[0]][vec[1]][vec[2]];
}
inline int work(std::vector<int> vec){
if(SZ(vec) == 1 && vec[0] == 1) return 0;
if(SZ(vec) <= 3 && calc(vec) != -1) return calc(vec);
int res = 1e9,n = SZ(vec);
int sm = 0;for(auto x:vec) sm += x;
if(!(sm&1)){
if(vec[0] >= sm/2){
std::vector<int> tmp;
if(vec[0] > sm/2) tmp.pb(vec[0]-sm/2);
FOR(i,1,SZ(vec)-1) tmp.pb(vec[i]);
// for(auto x:tmp) assert(x > 0);
res = std::min(res,work(tmp));
}
if(vec.back() >= sm/2){
std::vector<int> tmp;
FOR(i,0,SZ(vec)-2) tmp.pb(vec[i]);
if(vec.back() > sm/2) tmp.pb(vec.back()-sm/2);
// for(auto x:tmp) assert(x > 0);
res = std::min(res,work(tmp));
}
}
if(n >= 6) return res+1;
if(n == 5 && vec[1] == vec[3]){
res = std::min(res,work({vec[0],vec[1],vec[2]+vec[4]}));
res = std::min(res,work({vec[0]+vec[2],vec[3],vec[4]}));
}
if(n == 4){
if(vec[0] == vec[2]){
res = std::min(res,work({vec[0],vec[1]+vec[3]}));
res = std::min(res,work({vec[1],vec[2],vec[3]}));
}
if(vec[1] == vec[3]){
res = std::min(res,work({vec[0],vec[1],vec[2]}));
res = std::min(res,work({vec[0]+vec[2],vec[3]}));
}
}
if(n == 3){
if(!(vec[1]&1)) res = std::min(res,work({vec[0],vec[1]>>1,vec[2]}));
if(vec[0] == vec[2]) res = std::min(res,work({vec[1],vec[2]}));
if(vec[0] == vec[1]) res = std::min(res,work({vec[1],vec[2]}));
if(vec[1] == vec[2]) res = std::min(res,work({vec[0],vec[1]}));
if(vec[1] <= std::max(vec[0],vec[2])) res = std::min(res,work({sm-2*vec[1],vec[1]}));
}
if(n == 2){
if(!(vec[0]&1)) res = std::min(res,work({vec[0]>>1,vec[1]}));
if(!(vec[1]&1)) res = std::min(res,work({vec[0],vec[1]>>1}));
if(vec[0] == vec[1]) res = std::min(res,work({vec[0]}));
else{
int mn = std::min(vec[0],vec[1]);
res = std::min(res,work({mn,sm-2*mn}));
}
}
if(n == 1) if(vec[0]&1) res = std::min(res,work({vec[0]/2,1}));
++res;
if(n <= 3) calc(vec) = res;
return res;
}
int getNumber(std::string str){
std::vector<int> vec;int c = 0;
FOR(i,0,SZ(str)-1){
if(i > 0 && str[i] != str[i-1]) vec.pb(c),c = 0;
++c;
}
vec.pb(c);CLR(f,-1);
int res = work(vec);
// DEBUG(res);
// exit(0);
return res>=1e9?-1:res;
}
};
