前言
最近心血来潮学了一下这个套路？感觉很高级 qwq。
正文
我不好归纳，但他们大体都是一样的。
T1
题意
给定一个 \(N\) 行 \(M\) 列的字符矩阵。
我们定义一个字符矩阵的凌乱度为：
若这个字符矩阵中所有字符都相同，则凌乱度为 \(0\)。
否则，则考虑所有的沿水平或者竖直方向的直线，将字符矩阵分成两个不为空的部分，设两个部分的凌乱度分别为 \(a\) 和 \(b\)，则整个字符矩阵的凌乱度为 \(\max(a,b)+1\) 的最小值。
请你求出，给出的字符矩阵的凌乱度是多少。
\(1 \leq N, M \leq 185\)。
Solution
我学习的是 Alex_wei 的博客。在这里自己阐述一遍加深理解qaq。
先考虑答案上限，就是全不相同，每次从中间切开，所以上界是 \(O(\log n + \log m)\) 的。
首先考虑朴素 \(dp\)，形如 \(f[i][j][k][l]\) 为求出左上角 \((i,j)\) 右下角 \((k,l)\) 的答案。我们发现状态数就是 \(O(n^4)\) 的，转移复杂度很爆炸。
再进行一步观察发现一个显然的性质：
- 矩形之间存在包含关系的时候，答案一定不降。
再深入一点：
- 对于固定了左、上、下边界 \((i,j,k)\) 的矩形，随着右边界的增加答案不降。
于是考虑令 \(dp[i][j][k][x]\) 表示固定了左、上、下边界为 \((i,j,k)\) 的矩形，此时答案不超过 \(x\) 能到达的最右边界。
这实际上就是交换值域定义域了，非常巧妙，并且降低了复杂度，因为我们的答案是 \(O(\log)\) 级别的。
然后就是这个 \(x\) 因为每次最多加一，可以滚动数组，他没啥意义。
答案就是 \(dp[1][1][n] == m\) 的时候的 \(x\)。
下面的 \(f,g\) 是滚动数组。
转移分两种：
- 横着切类似区间 \(dp\) 的转移\[f[i][j][k] = max(min(g[i][j][p],g[i][p + 1][k])) \]
- 竖着切就类似倍增的转移\[f[i][j][k] = max(g[g[i][j][k] + 1][j][k]) \]
于是做完了 qaq 。
点击查看代码
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template <typename T,typename ...Args>
inline void read(T &tmp,Args &...tmps){read(tmp);read(tmps...);}
const int N = 190;
int n,m;
char s[N][N];
int f[N][N][N],ff[N][N][N];
int s1[N][N],s2[N][N];
inline int q1(int x1,int y1,int x2,int y2){
return s1[x2][y2] + s1[x1 - 1][y1 - 1] - s1[x2][y1 - 1] - s1[x1 - 1][y2];
}
inline int q2(int x1,int y1,int x2,int y2){
return s2[x2][y2] + s2[x1 - 1][y1 - 1] - s2[x2][y1 - 1] - s2[x1 - 1][y2];
}
signed main(){
read(n,m);
rep(i,1,n)scanf("%s",s[i] + 1);
rep(i,1,n)rep(j,1,m){
s1[i][j] = s1[i - 1][j] + s1[i][j - 1] - s1[i - 1][j - 1] + (s[i][j] == '#');
s2[i][j] = s2[i - 1][j] + s2[i][j - 1] - s2[i - 1][j - 1] + (s[i][j] == '.');
}
rep(k,1,m){
rep(l,1,n){
int now = m;
rep(r,l,n){
while(q1(l,k,r,now) && q2(l,k,r,now))--now;
f[k][l][r] = now;
}
}
}
for(int i = 0;; ++ i){
if(f[1][1][n] == m){
printf("%d\n",i);
return 0;
}
rep(k,1,m){
rep(l,1,n){
int p = l;
rep(r,l,n){
#define val(p) min(f[k][l][p],f[k][p + 1][r])
while(p + 1 < r && val(p) <= val(p + 1))++p;
ff[k][l][r] = max({val(p),f[k][l][r],f[f[k][l][r] + 1][l][r]});
}
}
}
swap(f,ff);
}
}
T2
题意
长度为 \(n\) 的序列，\(n \le 15\) ，每次可以进行操作形如：选择 \(i,j\)，令 \(a[j] += a[i]\) ，删除 \(a[i]\)，求令序列严格递增的最小次数并输出方案。
Solution
神仙题！！！
题意等价于将序列划分成若干个集合，使得最后可以排成一个严格单增的序列。
那么考虑 \(f[i][j][k]\) 为考虑完前 \(i\) 个集合，第 \(i\) 个集合全部加在了 \(j\) 的身上，已经用过的集合为 \(k\) 时，第 \(i\) 个集合的最小值。
转移的时候直接枚举没选过的集合是什么，扔进第 \(i + 1\) 个集合里面，并且要保证扔在 \(p\) 右边的最左边的位置。
同理答案就是，从大往小枚举 \(i\) ，如果存在答案，就是他了！直接输出路径即可qaq。
点击查看代码
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
template <typename T>
inline void read(T &x){
x=0;char ch=getchar();bool f=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=-x;
}
template <typename T,typename ...Args>
inline void read(T &tmp,Args &...tmps){read(tmp);read(tmps...);}
const int N = 20;
int n,a[N];
const int M = (1 << 15) + 5;
int s[M],dp[N][N][M],id[N];
using pii = pair<int,int>;
struct qwq{
int i,p,s;
};
#define endl putchar('\n')
#define spac putchar(' ')
template <typename T>
void write(T x){
if(x >= 10)write(x / 10);
putchar(x % 10 + '0');
}
qwq fa[N][N][M];
//dp[i][j][k]
//有i个集合，第i个都合并到j，已经选的集合为k，第i个集合最小值
const int INF = 0x3f3f3f3f;
#define pop(x) __builtin_ctz(x)
inline void ckmin(int &x,int y){if(x > y)x = y;}
inline void upd(qwq u,qwq v,int w){
ckmin(dp[v.i][v.p][v.s],w);
if(dp[v.i][v.p][v.s] == w)fa[v.i][v.p][v.s] = u;
}
inline void solve(){
read(n);
Rep(i,0,n)read(a[i]);
Rep(st,0,1 << n){
s[st] = 0;
Rep(j,0,n)if(st >> j & 1)s[st] += a[j];
}
rep(i,0,n)rep(j,0,n)Rep(k,0,1 << n)dp[i][j][k] = INF;
dp[0][0][0] = 0;
Rep(i,0,n)Rep(j,0,n)Rep(k,0,1 << n)if(dp[i][j][k] != INF){
qwq u = {i,j,k};
int st = (((1 << n) - 1) ^ k);
for(int s1 = st;s1;s1 = (s1 - 1) & st){
if(s[s1] > dp[i][j][k] && (s1 >> j)){
qwq v = {i + 1,j + 1 + pop(s1 >> j),k | s1};
upd(u,v,s[s1]);
}
}
}
qwq ans = (qwq){-1,-1,-1};
int to = (1 << n) - 1;
rrep(i,n,1){
rep(j,1,n)
if(dp[i][j][to] != INF){
ans = {i,j,to};
break;
}
if(~ans.i)break;
}
// printf("%d\n",n - ans.i);
write(n - ans.i);
endl;
Rep(i,0,n)id[i] = i + 1;
while(ans.i != 0){
qwq pre = fa[ans.i][ans.p][ans.s];
int s0 = pre.s ^ ans.s;
Rep(i,0,n){
if((s0 >> i & 1) && (i != ans.p - 1)){
// printf("%d %d\n",id[i],id[ans.p - 1]);
write(id[i]);spac;write(id[ans.p - 1]);endl;
Rep(j,i + 1,n)id[j]--;
}
}
ans = pre;
}
}
signed main(){
int t;
read(t);
while(t--)solve();
}