Chinaunix首页 | 论坛 | 博客

熟睡的企鹅finekill.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

zhln

  • 博客访问： 1558474
  • 博文数量： 327
  • 博客积分： 10000
  • 博客等级： 上将
  • 技术积分： 3556
  • 用 户 组： 普通用户
  • 注册时间： 2005-04-05 21:28
个人简介

东黑布衣，流浪幽燕。 真诚善良，值得信赖。

文章分类

全部博文（327）

我的朋友
推荐博文
相关博文
[20151205 PRO]

分类： BSD

2006-08-09 16:30:40

零件契合，两个零件形成一个4*4*H的长方体。
给定30000个零件，找出能形成的SUM(H)的最大值。

对于每个4*4的矩形M，先减去共有的底高，则每一位都是0-2
对于处理后的矩阵M1，与之对应的契合矩阵（每位也是0-2）是唯一的M2
M1和M2可以分别旋转三次，所得的4个矩阵都可与对方4个矩阵契合，每四个矩阵看做一个等价类
遍历30000个原始矩阵，用count数组记录其处理后矩阵等价类的出现次数，同时记录下处理前的底高。这样的等价类最多有60000个
遍历count数组，每两个等价类中分别依次取底高最高值作为可以契合的一对零件，直到一方取完

Ch数组记录等价类是否出现，每一维表示4*4数组的一行，由于每一位是0~2的三进制，所以每一维是3^4 = 81，其值为该等价类的processSeq
base数组记录每个零件的底高
processSeq记录数组处理序号，为0表示其等价类未处理过
mat数组用于计算契合数组

count[]数组每一行记录一个等价类，各位置含义：
0：为1表示该等价类出现过
1~8：表示底高为1~8的零件出现次数
9：该等价类与其契合等价类契合后的高度


  1. #include "stdafx.h"
  2. #include <iostream>
  3. #include <stdlib.h>

  5. #define MAX 30000
  6. #define P 81
  7. using namespace std;

  9. static int Ch[P][P][P][P];
  10. static int count[2 * MAX + 1][10];
  11. static int base[MAX];
  12. static int processSeq;
  13. static int mat[4][4];

  15. int processDelta(int delta[][4]) {
  16.     int i = 27 * delta[0][0] + 9 * delta[0][1] + 3 * delta[0][2] + delta[0][3];
  17.     int j = 27 * delta[1][0] + 9 * delta[1][1] + 3 * delta[1][2] + delta[1][3];
  18.     int k = 27 * delta[2][0] + 9 * delta[2][1] + 3 * delta[2][2] + delta[2][3];
  19.     int l = 27 * delta[3][0] + 9 * delta[3][1] + 3 * delta[3][2] + delta[3][3];

  21.     if (Ch[i][j][k][l] == 0) {
  22.         Ch[i][j][k][l] = processSeq;
  23.         return 0;
  24.     }
  25.     return Ch[i][j][k][l];
  26. }

  28. void rotate(int delta[][4]) {
  29.     int rot[4][4];
  30.     for (int i = 0; i < 4; i++) {
  31.         for (int j = 0; j < 4; j++) {
  32.             rot[i][j] = delta[3 - j][i];
  33.         }
  34.     }

  36.     for (int i = 0; i < 4; i++) {
  37.         for (int j = 0; j < 4; j++) {
  38.             delta[i][j] = rot[i][j];
  39.         }
  40.     }

  42.     return;
  43. }

  45. void match(int delta[][4], int max) {
  46.     for (int i = 0; i < 4; i++) {
  47.         for (int j = 0; j < 4; j++) {
  48.             mat[i][j] = max - delta[i][3 - j];
  49.         }
  50.     }
  51.     return;
  52. }

  54. int processCount() {
  55.     int result = 0;

  57.     for (int i = 1; i < MAX * 2; i += 2) {
  58.         if (count[i][0] == 1 && count[i + 1][0] == 1) {
  59.             int oddSum = 0, evenSum = 0;
  60.             for (int j = 1; j <= 8; j++) {
  61.                 oddSum += count[i][j];
  62.                 evenSum += count[i + 1][j];
  63.             }

  65.             int gap, idx, selection;
  66.             if (oddSum >= evenSum) {
  67.                 selection = evenSum;
  68.                 gap = oddSum - evenSum;
  69.                 idx = i;
  70.             } else {
  71.                 selection = oddSum;
  72.                 gap = evenSum - oddSum;
  73.                 idx = i + 1;
  74.             }
  75.             for (int j = 1; j <= 8; j++) {
  76.                 if (count[idx][j] > 0) {
  77.                     if (count[idx][j] > gap) {
  78.                         count[idx][j] -= gap;
  79.                         gap = 0;
  80.                     } else {
  81.                         gap -= count[idx][j];
  82.                         count[idx][j] = 0;
  83.                     }
  84.                     if (gap == 0) break;
  85.                 }
  86.             }

  88.             for (int j = 1; j <= 8; j++) {
  89.                 result += count[i][j] * j;
  90.                 result += count[i + 1][j] * j;
  91.             }

  93.             result += selection * count[i][9];
  94.         }
  95.     }

  97.     return result;
  98. }

  100. int test(int module[][4][4]) {
  101.     for (int a = 0; a < P; a++) {
  102.         for (int b = 0; b < P; b++) {
  103.             for (int c = 0; c < P; c++) {
  104.                 for (int d = 0; d < P; d++) {
  105.                     Ch[a][b][c][d] = 0;
  106.                 }
  107.             }
  108.         }
  109.     }

  111.     for (int i = 0; i < 2 * MAX + 1; i++) {
  112.         for (int j = 0; j < 10; j++) {
  113.             count[i][j] = 0;
  114.         }
  115.     }

  117.     processSeq = 1;
  118.     for (int i = 0; i < MAX; i++) {
  119.         int iBase = 8;
  120.         for (int j = 0; j < 4; j++) {
  121.             for (int k = 0; k < 4; k++) {
  122.                 if (module[i][j][k] < iBase)
  123.                     iBase = module[i][j][k];
  124.             }
  125.         }
  126.         base[i] = iBase;

  128.         int delta[4][4];
  129.         for (int j = 0; j < 4; j++) {
  130.             for (int k = 0; k < 4; k++) {
  131.                 delta[j][k] = module[i][j][k] - iBase;
  132.             }
  133.         }

  135.         int processed = processDelta(delta);
  136.         if (processed == 0) {
  137.             count[processSeq][0] = 1;
  138.             count[processSeq][base[i]]++;

  140.             for (int j = 0; j < 3; j++) {
  141.                 rotate(delta);
  142.                 processDelta(delta);
  143.             }

  145.             int max = 0;
  146.             for (int j = 0; j < 4; j++) {
  147.                 for (int k = 0; k < 4; k++) {
  148.                     if (delta[j][k] > max)
  149.                         max = delta[j][k];
  150.                 }
  151.             }
  152.             count[processSeq][9] = max;

  154.             processSeq++;
  155.             match(delta, max);
  156.             processDelta(mat);
  157.             for (int j = 0; j < 3; j++) {
  158.                 rotate(mat);
  159.                 processDelta(mat);
  160.             }

  162.             processSeq++;
  163.         } else {
  164.             count[processed][0] = 1;
  165.             count[processed][base[i]]++;
  166.         }
  167.     }

  169.     return processCount();
  170. }

  172. int main(void)
  173. {
  174.     static int module[MAX][4][4];//30000

  176.     srand(3); // 3 will be changed

  178.     for (int tc = 1; tc <= 10; tc++)
  179.     {
  180.         for (int c = 0; c < MAX; c++)
  181.         {
  182.             int base = 1 + (rand() % 6);//1~6
  183.             for (int y = 0; y < 4; y++)
  184.             {
  185.                 for (int x = 0; x < 4; x++)
  186.                 {
  187.                     module[c][y][x] = base + (rand() % 3);
  188.                 }
  189.             }
  190.         }
  191.         cout << "#" << tc << " " << test(module) << endl;
  192.     }

  194.     return 0;
  195. }




  1. #include <iostream>
  2. #include <stdlib.h>

  4. #define MAX 30000
  5. #define P 81
  6. using namespace std;

  8. static int Ch[P][P][P][P];
  9. static int count[MAX + 1][10];
  10. static int base[MAX];
  11. static int processSeq;
  12. static int mat[4][4];

  14. int processDelta(int delta[][4]) {
  15.    int i = 27 * delta[0][0] + 9 * delta[0][1] + 3 * delta[0][2] + delta[0][3];
  16.    int j = 27 * delta[1][0] + 9 * delta[1][1] + 3 * delta[1][2] + delta[1][3];
  17.    int k = 27 * delta[2][0] + 9 * delta[2][1] + 3 * delta[2][2] + delta[2][3];
  18.    int l = 27 * delta[3][0] + 9 * delta[3][1] + 3 * delta[3][2] + delta[3][3];
  19.    
  20.    if (Ch[i][j][k][l] == 0) {
  21.       Ch[i][j][k][l] = processSeq;
  22.       return 0;
  23.    }
  24.    return Ch[i][j][k][l];
  25. }

  27. void rotate(int delta[][4]) {
  28.    int rot[4][4];
  29.    for (int i = 0; i < 4; i++) {
  30.       for (int j = 0; j < 4; j++) {
  31.          rot[i][j] = delta[3 - j][i];
  32.       }
  33.    }

  35.    for (int i = 0; i < 4; i++) {
  36.       for (int j = 0; j < 4; j++) {
  37.        delta[i][j] = rot[i][j];
  38.       }
  39.    }
  40.    
  41.    return;
  42. }

  44. void match(int delta[][4], int max) {
  45.    for (int i = 0; i < 4; i++) {
  46.       for (int j = 0; j < 4; j++) {
  47.          mat[i][j] = max - delta[i][3 - j];
  48.       }
  49.    }
  50.    return;
  51. }

  53. int processCount() {
  54.    int result = 0;

  56.    for (int i = 1; i < MAX; i += 2) {
  57.       if (count[i][0] == 1 && count[i + 1][0] == 1) {
  58.          int oddSum = 0, evenSum = 0;
  59.          for (int j = 1; j <= 8; j++) {
  60.             oddSum += count[i][j];
  61.             evenSum += count[i + 1][j];
  62.          }

  64.          int gap, idx, selection;
  65.          if (oddSum >= evenSum) {
  66.             selection = evenSum;
  67.             gap = oddSum - evenSum;
  68.             idx = i;
  69.          } else {
  70.             selection = oddSum;
  71.             gap = evenSum - oddSum;
  72.             idx = i + 1;
  73.          }
  74.          for (int j = 1; j <= 8; j++) {
  75.             if (count[idx][j] > 0) {
  76.                if (count[idx][j] > gap) {
  77.                   count[idx][j] -= gap;
  78.                   gap = 0;
  79.                } else {
  80.                   gap -= count[idx][j];
  81.                   count[idx][j] = 0;
  82.                }
  83.                if (gap == 0) break;
  84.             }
  85.          }

  87.          for (int j = 1; j <= 8; j++) {
  88.             result += count[i][j] * j;
  89.             result += count[i + 1][j] * j;
  90.          }

  92.          result += selection * count[i][9];
  93.       }
  94.    }

  96.  return result;
  97. }

  99. int test2(int module[][4][4]) {
  100.    for (int a = 0; a < P; a++) {
  101.       for (int b = 0; b < P; b++) {
  102.          for (int c = 0; c < P; c++) {
  103.             for (int d = 0; d < P; d++) {
  104.                Ch[a][b][c][d] = 0;
  105.             }
  106.          }
  107.       }
  108.    }
  109.    
  110.    for (int i = 0; i < MAX + 1; i++) {
  111.       for (int j = 0; j < 10; j++) {
  112.          count[i][j] = 0;
  113.       }
  114.    }
  115.    
  116.    processSeq = 1;
  117.    for (int i = 0; i < MAX; i++) {
  118.       int iBase = 8;
  119.       for (int j = 0; j < 4; j++) {
  120.          for (int k = 0; k < 4; k++) {
  121.             if (module[i][j][k] < iBase)
  122.                iBase = module[i][j][k];
  123.          }
  124.       }
  125.       base[i] = iBase;
  126.       
  127.       int delta[4][4];
  128.       for (int j = 0; j < 4; j++) {
  129.          for (int k = 0; k < 4; k++) {
  130.             delta[j][k] = module[i][j][k] - iBase;
  131.          }
  132.       }
  133.       
  134.       int processed = processDelta(delta);
  135.       if (processed == 0) {
  136.          count[processSeq][0] = 1;
  137.          count[processSeq][base[i]]++;
  138.          
  139.          for (int j = 0; j < 3; j++) {
  140.             rotate(delta);
  141.             processDelta(delta);
  142.          }
  143.          
  144.          int max = 0;
  145.          for (int j = 0; j < 4; j++) {
  146.             for (int k = 0; k < 4; k++) {
  147.                if (delta[j][k] > max)
  148.                   max = delta[j][k];
  149.             }
  150.          }
  151.          count[processSeq][9] = max;
  152.          
  153.          processSeq++;
  154.          match(delta, max);
  155.          processDelta(mat);
  156.          for (int j = 0; j < 3; j++) {
  157.             rotate(mat);
  158.             processDelta(mat);
  159.          }
  160.          
  161.          processSeq++;
  162.       } else {
  163.          count[processed][0] = 1;
  164.          count[processed][base[i]]++;
  165.       }
  166.    }
  167.    
  168.    return processCount();
  169. }

  171. int main(void)
  172. {
  173.    static int module[MAX][4][4];
  174.    srand(3); // 3 will be changed
  175.    for (int tc = 1; tc <= 10; tc++)
  176.    {
  177.       for (int c = 0; c < MAX; c++)
  178.       {
  179.          int base = 1 + (rand() % 6);
  180.          for (int y = 0; y < 4; y++)
  181.          {
  182.             for (int x = 0; x < 4; x++)
  183.             {
  184.                module[c][y][x] = base + (rand() % 3);
  185.             }
  186.          }
  187.       }
  188.       cout << "#" << tc << " " << test2(module) << endl;
  189.    }

  191.    return 0;
  192. }








阅读(2379) | 评论(2) | 转发(0) |
0

上一篇：C语言的可变参数

下一篇：千字文

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6