解题思路
- 由于对于一点不知道后面得花费，所以无法决策当前是否要停下赚钱或要停下多久
- 考虑一点
，可以由其左上方的所有点
到达
- 所以从
- 然后考虑从
- 若存在，在
赚钱更优的情况，则会被从
- 因为处理
- 而
- 至于最优状态的选择
- 次数越少越好，在次数相同的情况下剩余钱越多越好
- 由于若次数少，可以通过增加次数换增加钱，所以次数的优先级更高
- 用
的
import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Objects;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.Vector;
//implements Runnable
public class Main{
static long md=(long)20020219;
static long Linf=Long.MAX_VALUE/2;
static int inf=Integer.MAX_VALUE/2;
static int M=10000;
static int N=300;
static int n=0;
static int m=0;
static int k=0;
static
class Node{
long x;//time
long y;//money
public Node() {
x=Linf;
y=0;
}
void get(long u,long v) {
x=u;
y=v;
}
}
public static void main(String[] args) throws Exception{
AReader input=new AReader();
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
int n=input.nextInt();
long[][] p=new long[n+1][n+1];
long[][] r=new long[n+1][n+1];
long[][] d=new long[n+1][n+1];
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
p[i][j]=input.nextLong();
}
}
for(int i=1;i<=n;++i) {
for(int j=1;j<n;++j) {
r[i][j]=input.nextLong();
}
}
for(int i=1;i<n;++i) {
for(int j=1;j<=n;++j) {
d[i][j]=input.nextLong();
}
}
Node[][] f=new Node[n+1][n+1];
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
f[i][j]=new Node();
}
}
f[1][1].get(0, 0);;
long[][] dis=new long[n+1][n+1];
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
for(int x=1;x<=i;++x) {
Arrays.fill(dis[x], Linf);
}
dis[i][j]=0;
for(int x=i;x>=1;--x) {
for(int y=j;y>=1;--y) {
if(x<i) dis[x][y]=Math.min(dis[x][y], d[x][y]+dis[x+1][y]);
if(y<j) dis[x][y]=Math.min(dis[x][y], r[x][y]+dis[x][y+1]);
long c=Math.max(0, dis[x][y]-f[x][y].y+(p[x][y]-1))/p[x][y];//上取整
long t=f[x][y].x+c+i-x+j-y;
long m=f[x][y].y+p[x][y]*c-dis[x][y];
if(t<f[i][j].x||t==f[i][j].x&&m>f[i][j].y) {
f[i][j].get(t, m);
}
}
}
}
}
out.print(f[n][n].x);
out.flush();
out.close();
}
// public static final void main(String[] args) throws Exception {
// new Thread(null, new Main(), "线程名字", 1 << 27).start();
// }
// @Override
// public void run() {
// try {
// //原本main函数的内容
// solve();
//
// } catch (Exception e) {
// }
// }
// static
// class Node{
// int x;
// int y;
// public Node(int u,int v) {
// x=u;
// y=v;
// }
// @Override
// public boolean equals(Object o) {
// if (this == o) return true;
// if (o == null || getClass() != o.getClass()) return false;
// Node may = (Node) o;
// return x == may.x && y==may.y;
// }
//
// @Override
// public int hashCode() {
// return Objects.hash(x, y);
// }
// }
static
class AReader{
BufferedReader bf;
StringTokenizer st;
BufferedWriter bw;
public AReader(){
bf=new BufferedReader(new InputStreamReader(System.in));
st=new StringTokenizer("");
bw=new BufferedWriter(new OutputStreamWriter(System.out));
}
public String nextLine() throws IOException{
return bf.readLine();
}
public String next() throws IOException{
while(!st.hasMoreTokens()){
st=new StringTokenizer(bf.readLine());
}
return st.nextToken();
}
public char nextChar() throws IOException{
//确定下一个token只有一个字符的时候再用
return next().charAt(0);
}
public int nextInt() throws IOException{
return Integer.parseInt(next());
}
public long nextLong() throws IOException{
return Long.parseLong(next());
}
public double nextDouble() throws IOException{
return Double.parseDouble(next());
}
public float nextFloat() throws IOException{
return Float.parseFloat(next());
}
public byte nextByte() throws IOException{
return Byte.parseByte(next());
}
public short nextShort() throws IOException{
return Short.parseShort(next());
}
public BigInteger nextBigInteger() throws IOException{
return new BigInteger(next());
}
public void println() throws IOException {
bw.newLine();
}
public void println(int[] arr) throws IOException{
for (int value : arr) {
bw.write(value + " ");
}
println();
}
public void println(int l, int r, int[] arr) throws IOException{
for (int i = l; i <= r; i ++) {
bw.write(arr[i] + " ");
}
println();
}
public void println(int a) throws IOException{
bw.write(String.valueOf(a));
bw.newLine();
}
public void print(int a) throws IOException{
bw.write(String.valueOf(a));
}
public void println(String a) throws IOException{
bw.write(a);
bw.newLine();
}
public void print(String a) throws IOException{
bw.write(a);
}
public void println(long a) throws IOException{
bw.write(String.valueOf(a));
bw.newLine();
}
public void print(long a) throws IOException{
bw.write(String.valueOf(a));
}
public void println(double a) throws IOException{
bw.write(String.valueOf(a));
bw.newLine();
}
public void print(double a) throws IOException{
bw.write(String.valueOf(a));
}
public void print(char a) throws IOException{
bw.write(String.valueOf(a));
}
public void println(char a) throws IOException{
bw.write(String.valueOf(a));
bw.newLine();
}
}
}
