ABC F AC19 WA12求调
  • 板块学术版
  • 楼主ICU152_lowa_IS8
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/9 21:43
  • 上次更新2024/3/9 23:15:03
查看原帖
ABC F AC19 WA12求调
933802
ICU152_lowa_IS8楼主2024/3/9 21:43
#include<bits/stdc++.h>
#define int long long
using namespace std;
int p[1005][1005];
int r[1005][1005];
int d[1005][1005];
struct node{
	int tmp;//剩余的钱数
	int ans;//要攒钱的次数
	int maxn;//之前的最大值
}dp[1005][1005];
signed main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>p[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<n;j++){
			cin>>r[i][j];
		}
	}
	for(int i=1;i<n;i++){
		for(int j=1;j<=n;j++){
			cin>>d[i][j];
		}
	}
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			dp[i][j].ans=0x3f3f3f3f3f3f3f3f;
			dp[i][j].tmp=0;
			dp[i][j].maxn=0;
		}
	}
//	memset(dp,0x3f,sizeof(dp));
	dp[1][1].tmp=0;
	dp[1][1].ans=0;
	dp[1][1].maxn=p[1][1];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==1&&j==1){
//				cout<<"0|0|0\t";
				continue;
			}
			int rans=dp[i][j-1].ans,rtmp=dp[i][j-1].tmp;
			if(rtmp<r[i][j-1]){
				rans+=(r[i][j-1]-rtmp+dp[i][j-1].maxn-1)/dp[i][j-1].maxn;
				rtmp=(r[i][j-1]-rtmp+dp[i][j-1].maxn-1)/dp[i][j-1].maxn*dp[i][j-1].maxn+rtmp-r[i][j-1];
			}
			else{
				rtmp-=r[i][j-1];
			}
			int dans=dp[i-1][j].ans,dtmp=dp[i-1][j].tmp;
			if(dtmp<d[i-1][j]){
				dans+=(d[i-1][j]-dtmp+dp[i-1][j].maxn-1)/dp[i-1][j].maxn;
				dtmp=(d[i-1][j]-dtmp+dp[i-1][j].maxn-1)/dp[i-1][j].maxn*dp[i-1][j].maxn+dtmp-d[i-1][j];
			}
			else{
				dtmp-=d[i-1][j];
			}
			if(rans<dans||rans==dans&&rtmp>dtmp||rans==dans&&rtmp==dtmp&&dp[i][j-1].maxn>dp[i-1][j].maxn){
				dp[i][j].maxn=max(dp[i][j-1].maxn,p[i][j]);
				dp[i][j].ans=rans;
				dp[i][j].tmp=rtmp;
			}
			else{
				dp[i][j].maxn=max(dp[i-1][j].maxn,p[i][j]);
				dp[i][j].ans=dans;
				dp[i][j].tmp=dtmp;
			}
		}
	}
	cout<<dp[n][n].ans+2*(n-1);
	return 0;
}
2024/3/9 21:43
加载中...