E. Vanya and Balloons Codeforces Round #355 (Div. 2)

http://codeforces.com/contest/677/problem/E

题意：有n*n矩形，每个格子有一个值（0、1、2、3），你可以在矩形里画一个十字（‘+’形或‘x’形），十字的四条边需等长。问十字覆盖的格子的值累乘最大是多少？

思路：

1、防止溢出，在比较大小更新答案时用加法替换乘法：a*b==log(a)+log(b)；

2、首先，遍历每个点，对于每个点，对8个方向dfs，直到越界或值为0；求出每个点各个方向的深度后，第二遍遍历时可以得到十字的长度，然后算出若以该点为中心点它的最大贡献，更新答案。

关键数组：

dep[dir][i][j]:以i、j为中心点，向方向dir走，最深能走多远；

sum[dir][i][j]:以i、j为中心点，向方向dir走，走到最深时这一路的贡献和；

优化：

同一个方向的dfs数据是可以重复利用的，如4-3-2-1，第一次dfs算出了3-2-1的数据，对于4来说，如果可以走，只要加上3的数据就可以结束4的dfs了；

备注：ans初始化应该为-1，0会错；不优化会超时；

 import java.io.*;

 import java.util.Arrays;

 public class a {

     private static final int c = 1010;

     static int[][][] dep = new int[8][c][c];

     static double[][][] sum = new double[8][c][c];

     static final int[] dx = {1, 0, -1, 0, 1, 1, -1, -1};

     static final int[] dy = {0, 1, 0, -1, 1, -1, -1, 1};

     static void dfs(int d, int x, int y) {

         if (dep[d][x][y] != -1) return;

         int xx = x + dx[d], yy = y + dy[d];

         if (Math.min(xx, yy) < 1 || Math.max(xx, yy) > n || a[xx][yy] == 0) {

             dep[d][x][y] = 1;

             sum[d][x][y] = lg[x][y];

             return;

         }

         dfs(d, xx, yy);

         dep[d][x][y] = dep[d][xx][yy] + 1;

         sum[d][x][y] = sum[d][xx][yy] + lg[x][y];

     }

     static int n;

     static int[][] a = new int[c][c];

     static double[][] lg = new double[c][c];

     public static void main(String[] args) {

         final int mod = (int) (1e9 + 7);

         IO io = new IO();//自己写的类，没有贴出来

         n = io.nextInt();

         for (int i = 0; i < dep.length; i++)

             for (int j = 0; j < dep[0].length; j++) Arrays.fill(dep[i][j], -1);

         int dis, rr = 0, cc = 0, res_dis = 0, res_s = 0;

         double cur, ans = -1;

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

             for (int j = 1; j <= n; j++) if ((a[i][j] = io.nextChar() - '0') != 0) lg[i][j] = Math.log(a[i][j]);

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

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

                 for (int k = 0; k < 8; k++) if (dep[k][i][j] == -1 && a[i][j] != 0) dfs(k, i, j);

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

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

                 if (a[i][j] != 0) for (int s = 0; s <= 1; s++) {

                     dis = c;

                     cur = lg[i][j];

                     for (int k = s * 4; k <= s * 4 + 3; k++) dis = Math.min(dis, dep[k][i][j]);

                     for (int k = s * 4; k <= s * 4 + 3; k++)

                         cur += sum[k][i][j] - lg[i][j] - sum[k][i + dis * dx[k]][j + dis * dy[k]];

                     if (cur > ans) {

                         ans = cur;

                         rr = i;

                         cc = j;

                         res_dis = dis;

                         res_s = s;

                     }

                 }

         if (res_dis == 0) {

             io.println(0);

             return;

         }

         long res = a[rr][cc];

         for (int i = 1; i <= res_dis - 1; i++)

             for (int t = res_s * 4; t <= res_s * 4 + 3; t++) res = res * a[rr + i * dx[t]][cc + i * dy[t]] % mod;

         io.println(res);

     }

 }

巴特西

E. Vanya and Balloons Codeforces Round #355 (Div. 2)

最新文章

热门文章