F 只 AC*7 求助

记录。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const ll N=85,INF=1e18;
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
inline void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)
	  write(x/10);
	putchar(x%10+'0');
}
ll n,ans=INF;
ll P[N][N],S[2][N][N];
pair<ll,ll> dp[N][N][N][N];
ll X[]={1,0},Y[]={0,1};
int main(){
	n=read();
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    P[i][j]=read();
	for(int i=1;i<=n;i++)
	  for(int j=1;j<n;j++)
	    S[0][i][j]=read();	
	for(int i=1;i<n;i++)
	  for(int j=1;j<=n;j++)
	    S[1][i][j]=read();	
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    for(int x=1;x<=i;x++)
	      for(int y=1;y<=j;y++)
	        dp[i][j][x][y]={INF,INF};
	dp[1][1][1][1]={0,0};
	for(int i=1;i<=n;i++){
	    for(int j=1;j<=n;j++){
		    for(int x=1;x<=i;x++){
		    	for(int y=1;y<=j;y++){
		    		if(dp[i][j][x][y].first>=INF)
		    		  continue;
		    		for(int k=0;k<2;k++){
				        ll dx=i+X[k],dy=j+Y[k],c=0,t=0;
				        if(dx>n||dy>n)
				          continue;
				        c=dp[i][j][x][y].second+S[k][x][y];
				        if(c>0){
				            t=(c+P[x][y]-1)/P[x][y];
				            c-=P[x][y]*t;
				        }
				        ll zx=x,zy=y;
				        if(P[zx][zy]<P[dx][dy]){
							zx=dx;
							zy=dy;
						}
						dp[dx][dy][zx][zy]=min(dp[dx][dy][zx][zy],{dp[i][j][x][y].first+t,c});
					} 
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    ans=min(ans,dp[n][n][i][j].first);
	write(ans+2*(n-1));
	return 0;
}