题解：P12613 [CCC 2025 Junior] Connecting Territories
This_is_my_choice
·
·
题解
终于有题解可以写了。
solution
虽然一眼 dp 但这题真的是橙吗？
题目大意其它题解有了我就不说了。
13pts 做法：
首先处理第一列和最后一列的特殊情况，可以将它们初始化为最大值，然后再推 dp 式子，很容易可以得出: dp[i][j]=\min(dp[i-1][j-1],\min(dp[i-1][j],dp[i-1][j+1]))+h
但是！
空间会超。
于是正解来了。
15pts 做法
可以使用滚动数组优化，因为它只需要上一行的数值，不用全部记录。
### AC CODE
```
#include<bits/stdc++.h>
using namespace std;
int dp[2][20005];
int main(){
//Write the code here
//Come
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int r,c,m;
cin>>r>>c>>m;
int mn=INT_MAX;
int h=0;
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
if(h+1>m){
h=1;
}else{
h++;
}
if(j>1){
dp[1][j]=min(dp[1][j],dp[0][j-1]);
}
if(j<c){
dp[1][j]=min(dp[1][j],dp[0][j+1]);
}
dp[1][j]+=h;
if(i==r){
mn=min(mn,dp[1][j]);
}
}
for(int j=1;j<=c;j++)dp[0][j]=dp[1][j];
}
cout<<mn;
return 0;
}
//LMAO
//Code by chc
```
## Thank you for reading!