我会二维dp了,但不会压缩成一维dp
  • 板块P1130 红牌
  • 楼主BensonChen
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/10/17 13:58
  • 上次更新2023/11/2 13:18:21
查看原帖
我会二维dp了,但不会压缩成一维dp
745442
BensonChen楼主2023/10/17 13:58

求大佬讲解

#include <bits/stdc++.h>

using namespace std;
long long n,m;
long long A[2003][2003];
long long dp[2003];
int main(){
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		for (int j=1;j<=n;j++){
			cin>>A[i][j];
		}
	}
	memset(dp,0x3f,sizeof(dp));
	dp[0]=0;
	int jnow=0;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			if(jnow==m&&j==1||jnow==j||abs(jnow-j)==1)/*dp[i]=min(dp[i],dp[i-1]+A[j][i]);*/{
				if(dp[i]>dp[i-1]+A[j][i])dp[i]=dp[i-1]+A[j][i];jnow=j;
			}
		}
	}
	cout<<dp[n];
	return 0;
}
2023/10/17 13:58
加载中...