题解：P12613 [CCC 2025 Junior] Connecting Territories

hear_the_wind · 2025-05-29 21:49:13 · 题解

题目也是非常明显，算法就是DP

分析

要想到当前格子是数量最小，则需要选上一行与当前格子共享一条边或一个角的格子。

• 不难得出 dp[i][j]=min(dp[i−1][j],min(dp[i−1][j−1],dp[0][j+1])))

• 但在第一列时，当前格子的左上格子不存在，所以当 j=1 时， dp[i][j]=min(dp[i−1][j],dp[i−1][j+1])

• 同理，在最后一行时，当前格子的右上格子不存在，所以当 j=c 时， dp[i][j]=min(dp[i−1][j],dp[i−1][j−1])

最后只需要记录最后一行的最小答案即可。

但这就结束了吗？

正当我自信满满地交代码时，空间超了！！！

仔细分析了一下，发现 R≤20000，C≤20000 ，空间超了。

优化

• 每一行的处理都只与上一行有关，所以可以用滚动数组来动态处理dp数组。

直接上代码

#include<bits/stdc++.h>
using namespace std;
int dp[2][20005];
int main(){
    int r,c,m;
    cin>>r>>c>>m;//输入
    int nowi=0,minn=INT_MAX;
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            if(++nowi>m) nowi=1;//如果大于最大值，那就变回1
            if(j==1) dp[1][j]=min(dp[0][j],dp[0][j+1]);//第一列的特殊情况
            else if(j==c) dp[1][j]=min(dp[0][j],dp[0][j-1]);//最后一列的特殊情况
            else dp[1][j]=min(dp[0][j],min(dp[0][j-1],dp[0][j+1]));//正常情况
            dp[1][j]+=nowi;//加上当前数
            if(i==r) minn=min(minn,dp[1][j]);//如果是最后一排则记录最小值 
        }
        for(int j=1;j<=c;j++) dp[0][j]=dp[1][j];//滚动更新
    }
    cout<<minn<<endl;//输出
    return 0;
}