codeforces 424D

题意：给定n,m<=300的矩阵，然后求一个长宽大于2的矩形，使得是从左上角位置开始逆时针绕边框一圈的时间最少。时间的计算是：给定3个数tu,tp, td，路径上数字增加为tu，相等为tp否则为td。

思路：直接预处理出4个数组，然后直接暴力。n⁴的方法。但是常数小可以4000+ms过。

还有一种n³logn的方法。。

具体是固定右下角，然后枚举右上角，然后通过一个通过地推维护一个前缀，二分查找。。

不过常数肯定比暴力大估计快不了多少。。

code：

 #include <bits/stdc++.h>

 #define M0(x) memset(x, 0, sizeof(x))

 #define repf(i, a, b) for(int i = (a); i <= (b); ++i)

 #define repd(i, a, b) for(int i = (a); i >= (b); --i)

 using namespace std;

 int U[][], D[][], L[][], R[][], a[][];

 int n, m;

 int tp, tu, td, t;

 inline int f(const int& a, const int& b){

      return a == b ? tp : (a > b ? tu : td);

 }

 void init(){

      scanf("%d%d%d", &tp, &tu, &td);

      M0(U), M0(D), M0(L), M0(R), M0(a);

      repf(i, , n) repf(j, , m) scanf("%d", &a[i][j]);

      repf(i, , n) repf(j, , m){

           D[i][j] = D[i-][j] + f(a[i][j], a[i-][j]);

           R[i][j] = R[i][j-] + f(a[i][j], a[i][j-]);

      }

      repd(i, n, ) repd(j, m, ){

           U[i][j] = U[i+][j] + f(a[i][j], a[i+][j]);

           L[i][j] = L[i][j+] + f(a[i][j], a[i][j+]);

      }

 }

 void solve(){

      int ansd = 0x3fffffff, ans = ;

      int lx, ly, rx, ry, d;

      int tmp;

      for (int x = ; x <= n; ++x)

          for (int y = ; y <= m; ++y)

              for (int x1 = x + ; x1 <= n; ++x1)

                  for (int y1 = y + ; y1 <= m; ++y1){

                       tmp = D[x1][y1] - D[x][y1] + U[x][y] - U[x1][y];

                       tmp += (R[x][y1] - R[x][y] + L[x1][y] - L[x1][y1]);

                       d = abs(tmp - t);

                       if (d < ansd || (d == ansd && tmp < ans)){

                            lx = x, ly = y;

                            rx = x1, ry = y1;

                            ansd = d, ans = tmp;

                       }

                  }

 //    cout <<ans << endl;

      printf("%d %d %d %d\n", lx, ly, rx, ry);

 }

 int main(){

 //    freopen("a.in", "r", stdin);

     while (scanf("%d%d%d", &n, &m, &t) != EOF){

           init();

           solve();

     }

     return ;

 }

巴特西

codeforces 424D

最新文章

热门文章