自动搬运

查看原文

来自洛谷，原作者为

	This_is_my_choice This is my choice.||ISFJ||看情况壶关，蓝名可来，不要再取关了

搬运于2025-08-24 23:16:51，当前版本为作者最后更新于2025-06-05 20:46:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

终于有题解可以写了。

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 做法

可以使用滚动数组优化，因为它只需要上一行的数值，不用全部记录。

$O(RC)$ 可以过，主要是优化空间。

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!