题解：P14680 [ICPC 2025 Yokohama R] Tatami Renovation
P14680 [ICPC 2025 Yokohama R] Tatami Renovation题解
题目传送门（Luogu）
“也可以考虑使用动态规划的方法，从第一列开始处理走廊。以当前列与下一列中地砖的摆放情况为状态，值为到目前为止最少移动的地砖数量，不过，这种方法的实现会相对复杂一些。” ——@AmaoFox的题解
喜欢赤石的我又来赤石了。
我们的 DP 宝宝一定是最可爱的啦
题目思路
本题等价于在一个
根据二分图匹配和由于网格宽度仅为
我们将网格进行黑白染色：对于格子
每一个榻榻米必定覆盖一个黑格和一个白格。因此，要存在完美匹配，任何前缀
由于地砖只能移动至多
关键性质：
经过任意多个连续且完全没有任何初始地砖（和地砖移动波及不到）的空列时，状态的差值
因此，我们可以仅将包含地砖的列及其左右相邻的列（即可能发生移动和覆盖的区域）提取出来作为活跃列（代码中 mov 数组）。
列与列之间巨大的空白断层则可以通过简单的状态继承直接跳过。
考虑动态规划。
对扫描到的每一列
对每一个状态记录最小移动次数。
对于列与列之间被跳过的空列，强制要求
#include<bits/stdc++.h>
#define endl '\n'
#define debug "-------------------\n"
#define rep(I, A, B) for (int I = (A); I <= (B); I++)
#define dwn(I, A, B) for (int I = (A); I >= (B); I--)
#define CleanIce __int128
#define bit_count(a) __builtin_popcount(a)
#define int long long
using namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f, mod = 998244353;
int add(int a, int b){ a += b; if(a >= mod) a %= mod; return a;}
int sub(int a, int b){ a -= b; if(a < 0) a += mod; return a;}
int mul(int a, int b){ if(b >= mod) b %= mod; if(a >= mod) a %= mod; a *= b; if(a >= mod) a %= mod; return a;}
void Min(int &a, int b){ if(b < a) a = b;}
void Max(int &a, int b){ if(b > a) a = b;}
template <typename T>
inline void read(T &x) {
x = 0; char c = getchar();
int f = 0;
for (; !isdigit(c); c = getchar()) f |= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
if (f) x = -x;
}
template <typename T, typename ...Args>
inline void read(T &x, Args &...args) {
read(x), read(args...);
}
template <typename T>
inline void write(T x, char ch) {
if (x < 0) x = -x, putchar('-');
static short st[70], tp;
do st[++tp] = x % 10, x /= 10; while (x);
while (tp) putchar(st[tp--] | 48);
putchar(ch);
}
template <typename T, typename ...Args>
inline void write(T x, char ch, Args ...args) {
write(x, ch), write(args...);
}
const int N = 2e5 + 5;
struct Node{
int nxt;
int c;
};
// g[i1][i2][parity][is_last][S]
vector<Node> g[3][3][3][3][55];
int r1[N];
int r2[N];
int mov[N * 3];
vector<int> get(int i, int l_in, int lst){
vector<int> ans;
if(i == 0){
if(l_in == 0) ans.push_back(0);
}else{
if(l_in == 1) ans.push_back(2);
else{
ans.push_back(1);
if(!lst) ans.push_back(3);
ans.push_back(4);
}
}
return ans;
}
void init(){
rep(i1, 0, 1){
rep(i2, 0, 1){
rep(par, 0, 1){
rep(lst, 0, 1){
rep(status, 0, 47){
int S = status / 16;
int r1 = (status / 8) % 2;
int r2 = (status / 4) % 2;
int l1 = (status / 2) % 2;
int l2 = status % 2;
auto c1s = get(i1, l1, lst);
auto c2s = get(i2, l2, lst);
for(int c1 : c1s){
for(int c2 : c2s){
int cost = (c1 != 1 && c1 != 0) + (c2 != 1 && c2 != 0);
int R1 = (c1 == 3);
int R2 = (c2 == 3);
int st1 = (c1 == 1);
int st2 = (c2 == 1); // stay
int cro1 = (c1 == 4);
int cro2 = (c2 == 4); // cross
int mxl1 = lst ? 0 : 1;
int mxl2 = lst ? 0 : 1;
rep(L1, 0, mxl1){
rep(L2, 0, mxl2){
int f1 = st1 + cro2 + r1 + L1;
int f2 = st2 + cro1 + r2 + L2;
if(f1 > 1 || f2 > 1) continue;
int e1 = 1 - f1;
int e2 = 1 - f2;
int b = par ? e1 : e2;
int w = par ? e2 : e1;
int Sval = S - 1;
if(Sval == 1 && w == 0) continue;
if(Sval == -1 && b == 0) continue;
Sval = Sval + b - w;
if(Sval < -1 || Sval > 1) continue;
Sval = Sval + 1;
int status_nxt = Sval * 16 + R1 * 8 + R2 * 4 + L1 * 2 + L2;
g[i1][i2][par][lst][status].push_back({status_nxt, cost});
}
}
}
}
}
}
}
}
}
}
int dp[55];
int ndp[55];
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
// ios::sync_with_stdio(0);
// cin.tie(0);
init();
int n;
int l;
read(n, l);
int c1 = 0;
int c2 = 0;
int m = 0;
rep(i, 1, n){
int r, c;
read(r, c);
if(r == 1) r1[++c1] = c;
else r2[++c2] = c;
if(c - 1 >= 1) mov[++m] = c - 1;
mov[++m] = c;
if(c + 1 <= l) mov[++m] = c + 1;
}
if(n & 1){
cout << "no" << endl;
return 0;
}
sort(r1 + 1, r1 + c1 + 1);
sort(r2 + 1, r2 + c2 + 1);
sort(mov + 1, mov + 1 + m);
int tot = 0;
rep(i, 1, m)
if(i == 1 || mov[i] != mov[i - 1]) mov[++tot] = mov[i];
m = tot;
rep(i, 0, 47) dp[i] = INF;
dp[16] = 0;
int pre = 0;
rep(i, 1, m){
int c = mov[i];
if(c > pre + 1){
rep(S, 0, 47) if(S % 16 != 0) dp[S] = INF;
}
int i1 = binary_search(r1 + 1, r1 + c1 + 1, c);
int i2 = binary_search(r2 + 1, r2 + c2 + 1, c);
int par = c & 1;
int lst = (c == l);
rep(i, 0, 47) ndp[i] = INF;
rep(S, 0, 47){
if(dp[S] == INF) continue;
for(auto tr : g[i1][i2][par][lst][S]){
Min(ndp[tr.nxt], dp[S] + tr.c);
}
}
rep(i, 0, 47) dp[i] = ndp[i];
pre = c;
}
if(pre < l){
rep(i, 0, 47) if(i % 16 != 0) dp[i] = INF;
}
int ans = dp[16];
if(ans >= INF) cout << "no" << endl;
else cout << ans << endl;
return 0;
}
/*
注释：
0 -- 这个位置保持空白
1、stay -- 这个格子的点停留在原地
2 --- 上一列已经向右伸出一个端点，当前列必须借助他
3 --- 向右延伸，要求下一列接住
4 cross --- 竖直连接上下两个格子
*/