专栏文章

题解：P12613 [CCC 2025 Junior] Connecting Territories

hhear_the_wind
P12613题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip6d4rm
此快照首次捕获于
2025/12/03 06:53
3 个月前
此快照最后确认于
2025/12/03 06:53
3 个月前
查看原文
题目也是非常明显，算法就是DP
分析
要想到当前格子是数量最小，则需要选上一行与当前格子共享一条边或一个角的格子。
  • 不难得出 dp[i][j]=min(dp[i−1][j],min(dp[i−1][j−1],dp[0][j+1])))dp[i][j]=min(dp[i−1][j],min(dp[i−1][j−1],dp[0][j+1])))
  • 但在第一列时，当前格子的左上格子不存在，所以当 j=1j=1 时， dp[i][j]=min(dp[i−1][j],dp[i−1][j+1])dp[i][j]=min(dp[i−1][j],dp[i−1][j+1])
  • 同理，在最后一行时，当前格子的右上格子不存在，所以当 j=cj=c 时， dp[i][j]=min(dp[i−1][j],dp[i−1][j−1])dp[i][j]=min(dp[i−1][j],dp[i−1][j−1])
最后只需要记录最后一行的最小答案即可。
但这就结束了吗？
正当我自信满满地交代码时，空间超了！！！
仔细分析了一下，发现 R≤20000，C≤20000R≤20000，C≤20000 ，空间超了。
优化
  • 每一行的处理都只与上一行有关，所以可以用滚动数组来动态处理dp数组。
直接上代码
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...