Codeforces 2096C Wonderful City 题解 [ 绿 ] [ 线性 DP ]

Wonderful City：整场卡在这道题上了，我糖丸了。

首先注意到每行每列只能操作一次，并且改变行的时候只会改变纵向相等的数，改变行的时候只会改变横向相等的数。所以我们可以对行和列分别操作。同时这个结论也可以通过差分理解。

因为对行和列操作做法是一样的，这里以行为例。

注意到如果某一行和前一行相邻的数存在小 \(1\) 的，就不能只操作这一行；如果某一行和前一行相邻的数存在大 \(1\) 的，就不能只操作前一行；如果某一行和前一行相邻的数存在相等的，就不能两行同时操作。

所以我们可以发现每一行有操不操作的这个 \(0/1\) 状态，于是设计 \(dp_{i,0/1}\) 表示考虑前 \(i\) 行，第 \(i\) 行不操作 / 操作的最小操作次数，规避掉前文所说的不合法情况转移即可。

时间复杂度 \(O(n^2)\)。

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define lc(x) (tr[x].ls)
#define rc(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldb;
using pi=pair<int,int>;
const int N=1005;
int n;
ll h[N][N],a[N],b[N],dp[N][2],ans=0;

void solve()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cin>>h[i][j];
        }
    }
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    memset(dp,0x3f,sizeof(dp));
    dp[1][0]=0;
    ans=0;
    dp[1][1]=a[1];
    for(int i=2;i<=n;i++)
    {
        int x=0,y=0,z=0;
        for(int j=1;j<=n;j++)
        {
            int cz=h[i][j]-h[i-1][j];
            if(cz==1)x=1;
            if(cz==0)y=1;
            if(cz==-1)z=1;
        }
        if(x==0)dp[i][0]=min(dp[i][0],dp[i-1][1]);
        if(y==0)dp[i][0]=min(dp[i][0],dp[i-1][0]);
        if(y==0)dp[i][1]=min(dp[i][1],dp[i-1][1]+a[i]);
        if(z==0)dp[i][1]=min(dp[i][1],dp[i-1][0]+a[i]);
    }
    ans+=min(dp[n][0],dp[n][1]);

    memset(dp,0x3f,sizeof(dp));
    dp[1][0]=0;
    dp[1][1]=b[1];
    for(int i=2;i<=n;i++)
    {
        int x=0,y=0,z=0;
        for(int j=1;j<=n;j++)
        {
            int cz=h[j][i]-h[j][i-1];
            if(cz==1)x=1;
            if(cz==0)y=1;
            if(cz==-1)z=1;
        }
        if(x==0)dp[i][0]=min(dp[i][0],dp[i-1][1]);
        if(y==0)dp[i][0]=min(dp[i][0],dp[i-1][0]);
        if(y==0)dp[i][1]=min(dp[i][1],dp[i-1][1]+b[i]);
        if(z==0)dp[i][1]=min(dp[i][1],dp[i-1][0]+b[i]);
    }
    ans+=min(dp[n][0],dp[n][1]);
    if(ans>=0x3f3f3f3f3f3f3f3f/2)cout<<-1<<'\n';
    else cout<<ans<<'\n';
}
int main()
{
    //freopen("sample.in","r",stdin);
    //freopen("sample.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}