30分求助
查看原帖
30分求助
531319
thomaswmy楼主2022/2/5 13:47

只A了2,3,4点

#include <bits/stdc++.h>
using namespace std;

int gcd(int a,int b) {
	if(b==0) return a;
	return gcd(b,a%b);
}

int lcm(int a,int b) {
	return a/gcd(a,b)*b;
}

int n,c[10000],h[2000][100],lm;
int dp[11000][1100];

int main() {
	scanf("%d",&n);
	c[0]=1;
	h[0][0]=0;
	c[n+1]=1;
	h[n+1][0]=0;
	lm=1;
	for(int i=1;i<=n;i++) {
		scanf("%d",&c[i]);
		lm=lcm(lm,c[i]);
		for(int j=1;j<=c[i]-1;j++) {
			scanf("%d",&h[i][j]);
		}
		scanf("%d",&h[i][0]);
	}
	memset(dp,0x7f,sizeof(dp));
	dp[1][0]=0;
	for(int i=0;i<=n;i++) {
		for(int j=0;j<lm;j++) {
			if(dp[j][i]!=2139062143) {
				dp[(j+1)%lm][i]=min(dp[(j+1)%lm][i],dp[j][i]+h[i][(j+1)%c[i]]);
				dp[(j+1)%lm][i+1]=min(dp[(j+1)%lm][i+1],dp[j][i]+h[i+1][(j+1)%c[i+1]]);
				if(i>0) dp[(j+1)%lm][i-1]=min(dp[(j+1)%lm][i-1],dp[j][i]+h[i-1][(j+1)%c[i-1]]);
//				printf("%d %d %d\n",i,j);
			}
		}
	}
	int ans=1e9;
	for(int i=0;i<lm;i++) {
//		printf("%d\n",dp[i][n+1]);
		ans=min(ans,dp[i][n+1]);
	}
	printf("%d",ans);
	return 0;
}
2022/2/5 13:47
加载中...