专栏文章

题解：CF2049D Shift + Esc

zzengxuheng
CF2049D题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqab4uk
此快照首次捕获于
2025/12/04 01:32
3 个月前
此快照最后确认于
2025/12/04 01:32
3 个月前
查看原文

分析

我们可以注意到每一行的调整是独立的，且调整次数的贡献是线性可拆的，考虑 DP\texttt{DP}。
因此令 dpi,j,kdp_{i,j,k} 为当前到达点 (x,y)(x,y)，并且第 ii 行向左移动了 kk 位，k∈[0,m−1]k \in [0,m-1]。
每次 dpi,j,kdp_{i,j,k} 仅可以从上一行 dpi−1,j,ldp_{i-1,j,l} 转移过来，l∈[0,m−1]l \in [0,m-1] 以及从 dpi,j−1,kdp_{i,j-1,k} 转移过来。
于是就得到一下转移方程：
dpi,j,k=min(dpi−1,j,l+k×K,dpi,j−1,k)+ai,(j+k−1) mod m+1dp_{i,j,k}=min(dp_{i-1,j,l}+k \times K,dp_{i,j-1,k})+a_{i,(j+k-1) \bmod m+1}
其中 KK 为题目中描述的 kk。
可是我们要循环枚举 ii，jj，kk，ll，时间复杂度为 O(nm3)O(nm^3)，超时了，还要优化。
我们发现，在 ll 这一维度是可以优化掉的。
由于一定要使 dpi−1,j,ldp_{i-1,j,l} 最小，可以在之前循环枚举到 (i−1,j)(i-1,j) 时记录最小的 dpi−1,j,kdp_{i-1,j,k} 即可。
我们将最小的 dpi,j,kdp_{i,j,k} 记为 fi,jf_{i,j}：
fi,j=min(dpi,j,k),k∈[0,m−1]f_{i,j}=min(dp_{i,j,k}),k \in [0,m-1]
那么转移方程变为：
dpi,j,k=min(fi−1,j+k×K,dpi,j−1,k)+ai,(j+k−1) mod m+1dp_{i,j,k}=min(f_{i-1,j}+k \times K,dp_{i,j-1,k})+a_{i,(j+k-1) \bmod m+1}
时间复杂度 O(nm2)O(nm^2)，可以通过。

Code

码风不正，请多多谅解。
CPP
#include<bits/stdc++.h>
using namespace std;
inline int read() {
	int x=0,f=1;
	char ch=getchar/*_unlocked*/();
	while (ch<48||ch>57) {
		if (ch=='-') f=-1;
		ch=getchar/*_unlocked*/();
	}
	while (ch>=48&&ch<=57) {
		x=x*10+ch-48;
		ch=getchar/*_unlocked*/();
	}
	return x*f;
}

template<typename T>
inline void write(T x,int f=1) {
	if(x<0) putchar/*_unlocked*/('-'),x=-x;
	if(x>9) write(x/10,0);
	putchar/*_unlocked*/(x%10+'0');
	if(f==1)putchar/*_unlocked*/('\n');
	if(f==2) putchar/*_unlocked*/(' ');
	return;
}
long long dp[310][310][310],f[310][310];
int a[310][310];

int main(){
	int t=read();
	while(t--){
		int n=read(),m=read(),k1=read();
		for(register int i = 1;i <= n;i++) for(register int j = 1;j <= m;j++) for(register int k = 0;k < m;k++) dp[i][j][k]=LONG_LONG_MAX;
		for(register int i = 1;i <= n;i++) for(register int j = 1;j <= m;j++) a[i][j]=read(),f[i][j]=LONG_LONG_MAX;
		for(register int i = 1;i <= n;i++) for(register int j = 1;j <= m;j++){
			if(i!=1||i==1&&j==1)for(register int l = 0;l < m;l++){
				dp[i][j][l]=min(dp[i][j][l],f[i-1][j]+a[i][(j+l-1)%m+1]+1ll*l*k1),f[i][j]=min(f[i][j],dp[i][j][l]);
			}
			if(j!=1)for(register int k = 0;k < m;k++){
				dp[i][j][k]=min(dp[i][j][k],dp[i][j-1][k]+a[i][(j+k-1)%m+1]),f[i][j]=min(f[i][j],dp[i][j][k]);
			} 
		}
		long long minn=1e18;
		for(register int i = 0;i < m;i++) minn=min(minn,dp[n][m][i]);
		write(minn);
	}
	return 0;
}
完结撒花。

评论

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

正在加载评论...