【Codeforces 429B】Working out

【链接】我是链接,点我呀:)

【题意】

两个人,一个人在左上角,一个人在左下角。
左上角要到右下角去
左下角要到右上角去
只能走到相邻的格子(不能往回走,即一个往右下,一个往右上走)
要求这两个人必须要在这个n*m的格子中选择一个格子作为休息点.
(两条路径只能有一个一样的点)
问最多能拿到多少分数(每个格子上有一个分数值)

【题解】

![](https://img2018.cnblogs.com/blog/1251265/201902/1251265-20190214171159886-1414539422.png)
会发现只有②和③不会重复走
则设f[p][i][j]分别为从左上、左下、右上、右下出发,到达点(i,j)的最大分数值
枚举休息点在什么地方
根据上图取答案的最大值就好

【代码】

import java.io.*;

import java.util.*;

public class Main {

	static InputReader in;

	static PrintWriter out;

	public static void main(String[] args) throws IOException{

		//InputStream ins = new FileInputStream("E:\\rush.txt");

		InputStream ins = System.in;

		in = new InputReader(ins);

		out = new PrintWriter(System.out);

		//code start from here

		new Task().solve(in, out);

		out.close();

	}

	static int N = (int)1e3;

	static class Task{

		public void solve(InputReader in,PrintWriter out) {

			int n,m;

			int [][]a = new int[N+10][N+10];

			int [][][]f = new int[4][N+10][N+10];

			n = in.nextInt();m = in.nextInt();

			for (int i = 1;i <= n;i++)

				for (int j = 1;j <= m;j++)

					a[i][j] = in.nextInt();

			//f[0]

			for (int i = 1;i <= n;i++)

				for (int j = 1;j <= m;j++)

					f[0][i][j] = Math.max(f[0][i-1][j], f[0][i][j-1])+a[i][j];

			//f[1]

			for (int i = 1;i <= n;i++)

				for (int j = m;j >= 1;j--)

					f[1][i][j] = Math.max(f[1][i-1][j], f[1][i][j+1])+a[i][j];

			//f[2]

			for (int i = n;i >= 1;i--)

				for (int j = 1;j <= m;j++)

					f[2][i][j] = Math.max(f[2][i][j-1], f[2][i+1][j])+a[i][j];

			//f[3]

			//f[0]

			for (int i = n;i >= 1;i--)

				for (int j = m;j >= 1;j--)

					f[3][i][j] = Math.max(f[3][i+1][j], f[3][i][j+1])+a[i][j];

			int ans = 0;

			for (int i = 1;i <= n;i++)

				for (int j = 1;j <= m;j++) {

					//(i,j)

					if (i>=2 && i<=n-1 && j>=2 && j <= m-1) {

						//plan 2

						int temp0,temp1,temp2,temp3;

						temp0 = f[0][i-1][j];

						temp1 = f[1][i][j+1];

						temp2 = f[2][i][j-1];

						temp3 = f[3][i+1][j];

						ans = Math.max(ans, temp0+temp1+temp2+temp3);

						//plan 3

						temp0 = f[0][i][j-1];

						temp1 = f[1][i-1][j];

						temp2 = f[2][i+1][j];

						temp3 = f[3][i][j+1];

						ans = Math.max(ans, temp0+temp1+temp2+temp3);

					}

				}

			out.println(ans);

		}

	}

	static class InputReader{

		public BufferedReader br;

		public StringTokenizer tokenizer;

		public InputReader(InputStream ins) {

			br = new BufferedReader(new InputStreamReader(ins));

			tokenizer = null;

		}

		public String next(){

			while (tokenizer==null || !tokenizer.hasMoreTokens()) {

				try {

				tokenizer = new StringTokenizer(br.readLine());

				}catch(IOException e) {

					throw new RuntimeException(e);

				}

			}

			return tokenizer.nextToken();

		}

		public int nextInt() {

			return Integer.parseInt(next());

		}

	}

}

巴特西

【Codeforces 429B】Working out

最新文章

热门文章