CF-1018-C. Wonderful City · znzryb
## 思路讲解
唉，dp，你说没想到吧，也想到了一点，但没往下深想。
唉，主要想错了，这个行和列是相互独立的。
其实就是出现两者之间相差一的情况，那么这个比较小的列就无法加一了。
但其实上面这个说法不全面，导致我的算法设计有瑕疵，比如说下面这个例子
```cpp
1
4
3 1 1 3 3 2 4 2
4 5 4 5 -> 4 6 -> 5 6
3 1 3 5 3 2 4 2
4 3 2 1 4 4 5 4
5 1 5 2
4 9 1 9
```
不难发现，上面这个例子还有可能传递，如第 $n$ 列需要 $+1$ 但是和第 $n-1$ 列相同了，所以第 $n-1$ 列也需要 $+1$ ，但 $n-1$ 列和第 $n-2$ 列相同了……。
当然，上面说了这么多，其实意思只有一个，就是不能以需要操作的行和列为主体，而应该以所有列为主体，因为操作行和列的操作可能导致其他行和列也需要操作。
不过，我们也发现行和列能怎么操作也只和相邻的行和列相关，那么如果按顺序转移也是可以的。
状态定义如下所列。
```cpp
// dpC[i][0] 表示保留第i列所需的最小花费
// dpC[i][1] 表示对第i列+1所需的最小花费
ll dpC[MAXN][2],dpR[MAXN][2];
```
转移只要确定是否合法其实就很简单了。
## AC代码
[https://codeforces.com/contest/2096/submission/318683142](https://codeforces.com/contest/2096/submission/318683142)
::: 源代码
```cpp
// Problem: C. Wonderful City
// Contest: Codeforces - Neowise Labs Contest 1 (Codeforces Round 1018, Div. 1 + Div. 2)
// URL: https://codeforces.com/contest/2096/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// by znzryb
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#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 getFro(vec) (vec.empty()?0:vec.front())
#define getBac(vec) (vec.empty()?0:vec.front())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define DEBUG(variable) \
do { \
std::cerr << #variable << ":"; \
for (const auto& elem : variable) { \
std::cerr << elem << " "; \
} \
std::cerr << "\n"; \
} while (0)
#define uniVec(var) \
do { \
sort(var.begin(),var.end());\
var.resize(unique(var.begin(),var.end())-var.begin());\
} while (0)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e3)+10,INF=static_cast<ll>(1e14)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;
ll N,M,K,T,A[MAXN],B[MAXN];
ll H[MAXN][MAXN];
// bool vaC[MAXN],vaR[MAXN];
ll dr[4]={1,0,-1,0};
ll dc[4]={0,-1,0,1};
// dpC[i][0] 表示保留第i列，dpC[i][1] 表示对第i列+1所需的最小花费
ll dpC[MAXN][2],dpR[MAXN][2];
inline void solve(){
cin>>N;
FOR(i,0,N+5){
dpC[i][0]=INF,dpC[i][1]=INF;
dpR[i][0]=INF,dpR[i][1]=INF;
FOR(j,0,N+5){
H[i][j]=INF;
}
}
FOR(i,1,N){
FOR(j,1,N){
cin>>H[i][j];
}
}
FOR(i,1,N){
cin>>A[i];
}
FOR(i,1,N){
cin>>B[i];
}
dpR[1][0]=0;
dpR[1][1]=A[1];
FOR(r,2,N){
bool zeroTo0=true;
FOR(c,1,N){
if(H[r][c]==H[r-1][c]){
zeroTo0=false;
break;
}
}
if(zeroTo0){
dpR[r][0]=min(dpR[r][0],dpR[r-1][0]);
}
bool zeroTo1=true;
FOR(c,1,N){
if(H[r-1][c]-H[r][c]==1){
zeroTo1=false;
break;
}
}
if(zeroTo1){
dpR[r][1]=min(dpR[r][1],dpR[r-1][0]+A[r]);
}
bool oneTo0=true;
FOR(c,1,N){
if(H[r-1][c]+1-H[r][c]==0){
oneTo0=false;
break;
}
}
if(oneTo0){
dpR[r][0]=min(dpR[r][0],dpR[r-1][1]);
}
bool oneTo1=true;
FOR(c,1,N){
if(H[r-1][c]-H[r][c]==0){
oneTo1=false;
break;
}
}
if(oneTo1){
dpR[r][1]=min(dpR[r][1],dpR[r-1][1]+A[r]);
}
}
dpC[1][0]=0;
dpC[1][1]=B[1];
FOR(c,2,N){
bool zeroTo0=true;
FOR(r,1,N){
if(H[r][c]==H[r][c-1]){
zeroTo0=false;
break;
}
}
if(zeroTo0){
dpC[c][0]=min(dpC[c][0],dpC[c-1][0]);
}
bool zeroTo1=true;
FOR(r,1,N){
if(H[r][c-1]-H[r][c]==1){
zeroTo1=false;
break;
}
}
if(zeroTo1){
dpC[c][1]=min(dpC[c][1],dpC[c-1][0]+B[c]);
}
bool oneTo0=true;
FOR(r,1,N){
if(H[r][c-1]+1-H[r][c]==0){
oneTo0=false;
break;
}
}
if(oneTo0){
dpC[c][0]=min(dpC[c][0],dpC[c-1][1]);
}
bool oneTo1=true;
FOR(r,1,N){
if(H[r][c-1]-H[r][c]==0){
oneTo1=false;
break;
}
}
if(oneTo1){
dpC[c][1]=min(dpC[c][1],dpC[c-1][1]+B[c]);
}
}
ll ans=min(dpR[N][1],dpR[N][0])+min(dpC[N][1],dpC[N][0]);
cout<<(ans>=INF?-1:ans)<<"\n";
#ifdef LOCAL
cerr<<"dpR:\n";
FOR(i,0,N){
cerr<<dpR[i][0]<<" ";
}
cerr<<"\n";
FOR(i,0,N){
cerr<<dpR[i][1]<<" ";
}
cerr<<"\n";
cerr<<"dpC:\n";
FOR(i,0,N){
cerr<<dpC[i][0]<<" ";
}
cerr<<"\n";
FOR(i,0,N){
cerr<<dpC[i][1]<<" ";
}
cerr<<"\n";
cerr<<"\n";
#endif
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--){
solve();
}
// solve();
return 0;
}
/*
AC
https://codeforces.com/contest/2096/submission/318683142
*/
```
:::
## 心路历程（WA，TLE，MLE……）