[关闭]
@LittleRewriter 2018-07-15T14:09:06.000000Z 字数 10405 阅读 808

lyd搜索专题

搜索

深搜及其优化

本节和lyd的顺序略错位。

深搜的含义与基本应用（0x22）

深搜的定义

深搜是一类包括遍历形式、状态记录与检索、剪枝优化等算法整体设计的统称。

深搜会形成一颗搜索树。我们将问题空间中的状态抽象成一个点，将访问两个状态的移动抽象为一条边，形成的树是搜索树。

整个深搜算法基于搜索树完成，为了避免重复访问，我们对状态进行记录检索；为了使程序更加高效，我们进行剪枝。

小猫爬山

...第一反应是状压DP我还有救么

状态是第now只猫使用了cnt架缆车，暴力枚举即可。

最优化剪枝是显然的；至于为什么先要从大到小排序？这样可以减少枚举次数。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  5. using namespace std;
  7. int cat[20], lc[20], W, n, ans;
  9. bool cmp(int a, int b) {return a > b;}
  11. void dfs(int cnt, int now) {
  12.     if(cnt >= ans) return;
  13.     if(now > n) {
  14.         ans = min(ans, cnt);
  15.         return;
  16.     }
  17.     for(int i = 1; i <= cnt; ++i) {
  18.         if(lc[i] + cat[now] <= W) {
  19.             lc[i] += cat[now];
  20.             dfs(cnt, now + 1);
  21.             lc[i] -= cat[now];
  22.         }
  23.     }
  24.     lc[cnt + 1] += cat[now];
  25.     dfs(cnt + 1, now + 1);
  26.     lc[cnt + 1] -= cat[now];
  27. }
  29. int main() {
  30.     scanf("%d%d", &n, &W);
  31.     for(int i = 1; i <= n; ++i) scanf("%d", &cat[i]);
  32.     ans = n;
  33.     sort(cat + 1, cat + 1 + n, cmp);
  34.     dfs(0, 1);
  35.     printf("%d", ans);
  36.     return 0;
  37. }

数独型搜索

luogu1784数独、POJ2676、POJ3074、luogu1074靶形数独、POJ3076

数据难度是递增的。。这次我们将数独型搜索的重点放在优化剪枝上。所以我先贴一下我好多年以前开O2才A掉的朴素靶形数独。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cctype>
  5. using namespace std;
  6. int map[11][11];
  7. int tensu[10][10] = 
  8. {
  9.     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  10.     {0, 6, 6, 6, 6, 6, 6, 6, 6, 6},
  11.     {0, 6, 7, 7, 7, 7, 7, 7, 7, 6},
  12.     {0, 6, 7, 8, 8, 8, 8, 8, 7, 6},
  13.     {0, 6, 7, 8, 9, 9, 9, 8, 7, 6},
  14.     {0, 6, 7, 8, 9, 10,9, 8, 7, 6},
  15.     {0, 6, 7, 8, 9, 9, 9, 8, 7, 6},
  16.     {0, 6, 7, 8, 8, 8, 8, 8, 7, 6},
  17.     {0, 6, 7, 7, 7, 7, 7, 7, 7, 6},
  18.     {0, 6, 6, 6, 6, 6, 6, 6, 6, 6}
  19. };
  20. int dijige[10][10] = 
  21. {
  22.     {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  23.     {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
  24.     {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
  25.     {0, 1, 1, 1, 2, 2, 2, 3, 3, 3},
  26.     {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
  27.     {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
  28.     {0, 4, 4, 4, 5, 5, 5, 6, 6, 6},
  29.     {0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
  30.     {0, 7, 7, 7, 8, 8, 8, 9, 9, 9},
  31.     {0, 7, 7, 7, 8, 8, 8, 9, 9, 9}
  32. };
  33. bool geneivis[11][11],hangvis[11][11], lievis[11][11];
  34. inline void read(int& x) {
  35.     x = 0; char c = getchar();
  36.     while(!isdigit(c)) c = getchar();
  37.     while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
  38. }
  39. int xx, yy, maxn = -1, ori;
  40. void printmap() {
  41.     for(int i = 1; i <= 9; ++i) {
  42.         for(int j = 1; j <= 9; ++j) {
  43.             printf("%d", map[i][j]);
  44.         }
  45.         printf("\n");
  46.     }
  47.     printf("\n");
  48. }
  49. void printvis() {
  50.     printmap();
  51.     for(int i = 1; i <= 9; ++i) {
  52.         for(int j = 1; j <= 9; ++j) {
  53.             cout<<hangvis[i][j]<<" ";
  54.         }
  55.         cout<<endl;
  56.     }
  57.     cout<<endl;
  58.     for(int i = 1; i <= 9; ++i) {
  59.         for(int j = 1; j <= 9; ++j) {
  60.             cout<<hangvis[i][j]<<" ";
  61.         }
  62.         cout<<endl;
  63.     }
  64.     cout<<endl;
  65.     for(int i = 1; i <= 9; ++i) {
  66.         for(int j = 1; j <= 9; ++j) {
  67.             cout<<geneivis[i][j]<<" ";
  68.         }
  69.         cout<<endl;
  70.     }
  71.     cout<<endl;
  72. }
  73. inline void dfs(register int x, register int y, register int ans, register int mark) {
  74.     if(ans + mark * 90 <= maxn) return;
  75.     //cout<<x<<" "<<y<<" "<<ans<<endl;
  76.     //if(x < 1 || y < 1 || x > 9 || y > 9) return;
  77.     if(x == 0) {
  78.         //printmap();
  79.         maxn = max(ans, maxn);
  80.         return;
  81.     }
  82.     if(!map[x][y]){
  83.         for(register int i = 9; i >= 1; --i) {   
  84.             //if(xx < 1 || yy < 1 || xx > 9 || yy > 9) continue;
  85.             //if(x == 7 && y == 9)printvis();
  86.             if(!hangvis[x][i] && !lievis[y][i] && !geneivis[dijige[x][y]][i]) {
  87.                 hangvis[x][i] = 1, lievis[y][i] = 1, geneivis[dijige[x][y]][i] = 1;
  88.                 map[x][y] = i;
  89.                 //cout<<"i:"<<i<<" "<<x<<" "<<y<<endl;
  90.                 //printmap();
  91.                 if(y > 1) dfs(x, y-1, ans + tensu[x][y] * i, mark - 1);
  92.                 else dfs(x-1, 9, ans + tensu[x][y] * i, mark - 1);
  93.                 hangvis[x][i] = 0, lievis[y][i] = 0, geneivis[dijige[x][y]][i] = 0;
  94.                 map[x][y] = 0;
  95.             }
  97.         }
  98.     }else {
  99.         if(y > 1) dfs(x, y-1, ans + tensu[x][y] * map[x][y], mark - 1);
  100.         else dfs(x-1, 9, ans + tensu[x][y] * map[x][y], mark - 1);
  101.     }
  102.     return;
  103. }
  104. int main() {
  105.     //freopen("test.txt", "w", stdout);
  106.     for(int i = 1; i <= 9; ++i) {
  107.         for(int j = 1; j <= 9; ++j) {
  108.             read(map[i][j]);
  109.         }
  110.     }
  111.     for(int i = 1; i <= 9; ++i) {
  112.         for(int j = 1; j <= 9; ++j) {
  113.             if(map[i][j]) {
  114.                 hangvis[i][map[i][j]] = 1;
  115.                 lievis[j][map[i][j]] = 1;
  116.                 geneivis[dijige[i][j]][map[i][j]] = 1;
  117.             }
  118.         }
  119.     }
  120.     dfs(9, 9, 0, 81);
  121.     printf("%d\n", maxn);
  122.     return 0;
  123. }

...是不是觉得非常壮观。这道题非常的经典，因此我联赛前专门做了它锻炼码力，虽说毫无卵用。

这道题有一个玄学优化：就是倒着搜。这样做的原因是出题人会专门卡正着搜；但是即便如此，除非结合卡时，否则还是会T在11点。即便开了O2，11点还是跑了956ms。可见非常玄学。

所以我们迫切的需要一些不那么玄学的剪枝来A掉。当然，有种数据结构叫做Dancing links可以解决这类问题；但是我个人是很讨厌数据结构而且这个东西不好学，所以我们不做讨论。

首先，我们应当有一个原则，就是从可能性最小的分支开始搜索。我们可以在一开始就扫一遍，把能填上的先填上；然后考虑每一行、每一列、每个九宫格，看看能不能填。

其次，对于某些点，我们可以用位运算优化。将行列九宫格的数用九位二进制数保存，这样的话按位与之后得到的结果就是可填的东西，枚举起来非常方便。

然后luogu那道题我们就可以这么0msA掉了

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  5. using namespace std;
  7. #define ri register int
  9. int belong[9][9] = {
  10. {0, 0, 0, 1, 1, 1, 2, 2, 2},
  11. {0, 0, 0, 1, 1, 1, 2, 2, 2},
  12. {0, 0, 0, 1, 1, 1, 2, 2, 2},
  13. {3, 3, 3, 4, 4, 4, 5, 5, 5},
  14. {3, 3, 3, 4, 4, 4, 5, 5, 5},
  15. {3, 3, 3, 4, 4, 4, 5, 5, 5},
  16. {6, 6, 6, 7, 7, 7, 8, 8, 8},
  17. {6, 6, 6, 7, 7, 7, 8, 8, 8},
  18. {6, 6, 6, 7, 7, 7, 8, 8, 8}
  19. };
  21. int sodoku[10][10], row[10], col[10], gri[10], tot;
  22. int cnt[1 << 10], num[1 << 10];
  24. inline void cha(int x, int y, int z) {
  25.     row[x] ^= 1 << z;
  26.     col[y] ^= 1 << z;
  27.     gri[ belong[x][y] ] ^= 1 << z;
  28. }
  30. inline bool dfs(int now) {
  31.     if(!now) return 1;
  32.     ri val, tag = 10; int x, y; //tag表示可能性，可能性不可能超过10个 
  33.     for(ri i = 0; i < 9; ++i) {
  34.         for(ri j = 0; j < 9; ++j) { //选取可能性最低的点 
  35.             //cout<<i<<" "<<j<<" "<<sodoku[i][j]<<endl;
  36.             if(sodoku[i][j] != 0) continue;
  37.             val = row[i] & col[j] & gri[ belong[i][j] ];
  38.             //if(now == 60) cout<<i<<" "<<j<<" "<<row[i]<<" "<<col[j]<<" "<<belong[i][j]<<" "<<gri[ belong[i][j] ]<<endl;
  39.             if(!val) return 0; //如果某一个点不能放，该决策错误 
  40.             if(cnt[val] < tag) {   
  41.                 tag = cnt[val];
  42.                 x = i, y = j;
  43.             }
  44.         }
  45.     }
  46.     val = row[x] & col[y] & gri[ belong[x][y] ];
  47.     ri tmp;
  48.     for(int qwq = val; qwq; qwq -= qwq & -qwq) {
  49.         tmp = num[qwq & -qwq];
  50.         sodoku[x][y] = tmp + 1;
  51.         cha(x, y, tmp);
  52.         if(dfs(now - 1)) return 1;
  53.         cha(x, y, tmp);
  54.         sodoku[x][y] = 0;
  55.     }
  56.     return 0;
  57. }
  59. int main() {
  60.     for(int i = 0; i < 9; ++i) 
  61.         row[i] = col[i] = gri[i] = (1 << 9) - 1,
  62.         num[1 << i] = i;
  63.     for(int i = 0; i < 1 << 9; ++i)
  64.         for(int j = i; j; j -= j&-j) cnt[i]++;
  65.     for(int i = 0; i < 9; ++i) 
  66.         for(int j = 0; j < 9; ++j)
  67.             cin>>sodoku[i][j];
  68.     for(int i = 0; i < 9; ++i) {
  69.         for(int j = 0; j < 9; ++j) {
  70.             if(sodoku[i][j]) cha(i, j, sodoku[i][j] - 1);
  71.             else ++tot;
  72.         }
  73.     }
  74.     /*for(int i = 0; i < (1 << 9); ++i) cout<<cnt[i]<<" ";
  75.     puts("");
  76.     for(int i = 0; i < (1 << 9); ++i) cout<<num[i]<<" ";
  77.     puts("");
  78.     for(int i = 0; i < 9; ++i) cout<<row[i]<<" ";
  79.     puts("");
  80.     for(int i = 0; i < 9; ++i) cout<<col[i]<<" ";
  81.     puts("");
  82.     for(int i = 0; i < 9; ++i) cout<<gri[i]<<" ";
  83.     puts("");*/
  84.     dfs(tot);
  85.     for(int i = 0; i < 9; ++i) {
  86.         for(int j = 0; j < 9; ++j)
  87.             cout<<sodoku[i][j]<<" ";
  88.         cout<<endl;
  89.     }
  90.     return 0;
  91. }

。。至于POJ3076什么的无能为力我直接扔lyd写了6k的代码了

  1. #include <stdio.h>
  2. #define EMPTY -1
  4. char map[16][16];
  5. unsigned short table[16][16];
  6. int filled;
  8. void fill (int i, int j, int a)
  9. {
  10.     int r, c, k, m;
  11.     filled++;
  12.     map[i][j] = a;
  13.     for (k = 0; k < 16; k++)
  14.         table[i][k] |= (1 << (a - 1)), table[k][j] |= (1 << (a - 1));
  15.     r = (int)(i / 4) * 4;
  16.     c = (int)(j / 4) * 4;
  17.     for (k = 0; k < 4; k++)
  18.     {
  19.         for (m = 0; m < 4; m++)
  20.             table[r + k][c + m] |= (1 << (a - 1));
  21.     }
  22.     return;
  23. }
  25. int search ()
  26. {
  27.     char t_map[16][16];
  28.     unsigned short t_table[16][16]; int t_filled;
  29.     int i, j, k, m, r, c, r1, r2, t0, t, flag;
  31.     if (filled == 256) return 1;
  33.     for (i = 0; i < 16; i++)
  34.     {
  35.         for (j = 0; j < 16; j++)
  36.         {
  37.             if (map[i][j]) continue;
  38.             r = -1;
  39.             for (k = 0; k < 16; k++)
  40.             {
  41.                 if (((table[i][j] & (1 << k)) == 0) && r == -1) r = k;
  42.                 else if (((table[i][j] & (1 << k)) == 0) && r != -1) { r = -2; break; }
  43.             }
  44.             if (r == -1) return 0;
  45.             else if (r != -2) fill(i, j, r + 1);
  46.         }
  47.     }
  49.     for (i = 0; i < 16; i++)
  50.     {
  51.         for (k = 0; k < 16; k++)
  52.         {
  53.             r = -1;
  54.             for (j = 0; j < 16; j++)
  55.             {
  56.                 if (map[i][j] == k + 1) { r = -2; break; }
  57.                 if (map[i][j]) continue;
  58.                 if (((table[i][j] & (1 << k)) == 0) && r == -1) r = j;
  59.                 else if (((table[i][j] & (1 << k)) == 0) && r != -1) { r = -2; break; }
  60.             }
  61.             if (r == -1) return 0;
  62.             else if (r != -2) fill(i, r, k + 1);
  63.         }
  64.     }
  66.     for (j = 0; j < 16; j++)
  67.     {
  68.         for (k = 0; k < 16; k++)
  69.         {
  70.             r = -1;
  71.             for (i = 0; i < 16; i++)
  72.             {
  73.                 if (map[i][j] == k + 1) { r = -2; break; }
  74.                 if (map[i][j]) continue;
  75.                 if (((table[i][j] & (1 << k)) == 0) && r == -1) r = i;
  76.                 else if (((table[i][j] & (1 << k)) == 0) && r != -1) { r = -2; break; }
  77.             }
  78.             if (r == -1) return 0;
  79.             else if (r != -2) fill(r, j, k + 1);
  80.         }
  81.     }
  83.     for (r = 0; r < 16; r += 4)
  84.     {
  85.         for (c = 0; c < 16; c += 4)
  86.         {
  87.             for (k = 0; k < 16; k++)
  88.             {
  89.                 r1 = -1, r2 = -1;
  90.                 for (i = 0; i < 4; i++)
  91.                 {
  92.                     for (j = 0; j < 4; j++)
  93.                     {
  94.                         if (map[r + i][c + j] == k + 1) { r1 = r2 = -2; goto outerloop1; }
  95.                         if (map[r + i][c + j]) continue;
  96.                         if (((table[r + i][c + j] & (1 << k)) == 0) && r1 == -1) r1 = r + i, r2 = c + j;
  97.                         else if (((table[r + i][c + j] & (1 << k)) == 0) && r1 != -1)
  98.                             { r1 = r2 = -2; goto outerloop1; }
  99.                     }
  100.                 }
  101.                 outerloop1: 
  102.                 if (r1 == -1) return 0;
  103.                 else if (r1 != -2) fill(r1, r2, k + 1);
  104.             }
  105.         }
  106.     }
  108.     if (filled == 256) return 1;
  110.     for (i = 0; i < 16; i++)
  111.     {
  112.         for (j = 0; j < 16; j++)
  113.             t_map[i][j] = map[i][j];
  114.     }
  115.     for (i = 0; i < 16; i++)
  116.     {
  117.         for (j = 0; j < 16; j++)
  118.             t_table[i][j] = table[i][j];
  119.     }
  120.     t_filled = filled;
  122.     t0 = 256;
  123.     for (i = 15; i >= 0; i--)
  124.     {
  125.         for (j = 15; j >= 0; j--)
  126.         {
  127.             if (map[i][j]) continue;
  128.             t = 0;
  129.             for (k = 0; k < 16; k++)
  130.             {
  131.                 if ((table[i][j] & (1 << k)) == 0) t++;
  132.                 if (t >= t0) break;
  133.             }
  134.             if (t < t0)
  135.             {
  136.                t0 = t;
  137.                r1 = i, r2 = j;
  138.             }
  139.         }
  140.     }
  142.     outerloop2:
  143.     for (m = 0; m < 16; m++)
  144.     {
  145.         if ((table[r1][r2] & (1 << m)) == 0)
  146.         {
  147.             fill(r1, r2, m + 1);
  148.             flag = search();
  149.             if (flag == 1) return 1;
  150.             else
  151.             {
  152.                 for (i = 0; i < 16; i++)
  153.                 {
  154.                     for (j = 0; j < 16; j++)
  155.                         map[i][j] = t_map[i][j];
  156.                 }
  157.                 for (i = 0; i < 16; i++)
  158.                 {
  159.                    for (j = 0; j < 16; j++)
  160.                        table[i][j] = t_table[i][j];
  161.                }
  162.                filled = t_filled;
  163.             }
  164.         }
  165.     }
  167.     return 0;
  168. }
  170. int main ()
  171. {
  172.     int i, j, k, m, r, c, a;
  173.     char ar[60];
  175.     while (1)
  176.     {
  178.     memset(map, 0, sizeof(map));
  179.     memset(table, 0, sizeof(table));
  180.     filled = 0;
  182.     for (i = 0; i < 16; i++)
  183.     {
  184.         if (scanf("%s", ar) != 1) goto end;
  185.         for (j = 0; j < 16; j++)
  186.         {
  187.             a = ar[j];
  188.             if (a == '-') continue;
  189.             else fill(i, j, a - 64);
  190.         }
  191.     }
  193.     search();
  194.     for (i = 0; i < 16; i++)
  195.     {
  196.         for (j = 0; j < 16; j++)
  197.             printf("%c", map[i][j] + 64);
  198.         printf("\n");
  199.     } printf("\n");
  201.     }
  202.     end: return 0;
  203. }

剪枝（0x23）

有六种常用剪枝方法。

第一种是卡时。卡时对最优化的深搜问题的非常有效的。

第二种是优化搜索顺序。我们可以去搜索玄学意义上更好的分支来达到效果；一般来说，可能性越小的分支应该越早的搜索。

第三章是排除等效冗余。下面会见到，一般来说对于重复子问题可以说这是很好用的。

第四种是可行性剪枝。如果说一个分支届到了边界，或者是不可能到达边界，我们就直接剪掉。比如刚才我们在数独型搜索中剪的那个。

第五种是最优性剪枝。比如在靶形数独的时候，我们搜到一个状态大于当前的最小状态，我们可以直接扔掉。

最后一种是记忆化。

POJ1011 Sticks

我们考虑这样一个状态设计。设木棒长度为k，那么，换言之我们的枚举范围是sum的所有约数。

我们的搜索状态是三维的代表第now个容器在对第wit进行搜寻，并且已经放了cap个。

先排序。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <vector>
  7. using namespace std;
  9. int n, stick[80], sum, mas;
  10. vector<int> v;
  11. int cer[80];
  12. bool vis[80];
  14. bool cmp(int a, int b) {
  15.     return a > b;
  16. }
  18. bool dfs(int val, int cap, int wit, int now) {
  19.     //if(val == 227) cout<<cap<<" "<<wit<<" "<<now<<endl;
  20.     if(now > (sum / val)) {
  21.         return true;
  22.     }
  23.     if(cap == val) return dfs(val, 0, 1, now + 1);
  24.     int fail = 0;
  25.     for(int i = wit; i <= n; ++i) { /*第一处*/
  26.         if(!vis[i] && cap + stick[i] <= val && stick[i] != fail) {
  27.             vis[i] = 1;
  28.             if(dfs(val, cap + stick[i], i + 1, now))
  29.                 return true;
  30.             fail = stick[i]; /*第二处*/
  31.             vis[i] = 0;
  32.             if(cap == 0) return false; /*第三处*/
  33.         }
  34.     }
  35.     return false;
  36. }
  39. int main() {
  40.     //freopen("biao.txt", "w", stdout);
  41.     while(cin>>n) {
  42.         if(!n) break; sum = 0; mas = 0;
  43.         for(int i = 1; i <= n; ++i) 
  44.             scanf("%d", &stick[i]), sum += stick[i], mas = max(mas, stick[i]);
  45.         sort(stick + 1, stick + 1 + n, cmp);
  46.         //for(int i = 1; i <= n; ++i) cout<<stick[i]<<" ";
  47.         int ans;
  48.         for(int i = mas; i <= sum; ++i) {
  49.             //cout<<i<<" ";
  50.             if(sum % i) continue;
  51.             memset(vis, 0, sizeof vis);
  52.             if(dfs(i, 0, 1, 1)) {
  53.                 ans = i;
  54.                 break;
  55.             }
  56.         }
  57.         cout<<ans<<endl;
  58.     }
  59. }

关注我专门圈住的三处。

第一处的含义是，对于递减排列的棍子来说，某一个格不能放就代表这个格以前的都不能放。

第二处的含义是，如果在搜索某一状态时有相同的a,b两个木棍且a不能放那么b一定不能放。

第三处的含义是，如果一个也放不进去，就说明该状态一定会出锅，直接减掉。

luogu1371/POJ1190/NOI1999 生日蛋糕

很棒的搜索题。

首先，我们从下往上倒序递归。

当然有个结论：所有的表面积=最下层蛋糕的表面积+所有层侧面积。

我们制定状态表示在搜索dep层时候的外表面积为S、体积为V。那么我们可以发现：

1，搜索范围

对于当前状态而言，首先搜索范围一定是

，

考虑到对于当前状态有，显然有，，然后就得到了第一个剪枝。

注意这里搜索应该倒序搜索。

2，可行性剪枝

假定对于第层，我们预处理一个最小的表面积和体积，维护h与r均取时前dep层达到的最小值。如果就代表不可行。

3，最优性剪枝

这个略复杂...

首先如果已经比搜到的答案大我们直接剪枝。

考虑公式。我们知道从1~dep - 1层的体积有，表面积为

我们稍微变形一下。考虑到

因此我们直接比较与当前最优解即可。

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <cmath>
  6. #include <vector>
  8. using namespace std;
  10. typedef long long LL;
  12. const LL INF = 0x3f3f3f;
  14. LL smin[18], vmin[18];
  15. LL pr[18], ph[18];
  16. LL N, M, ans = INF;
  18. void preope() {
  19.     for(int i = 1; i <= 16; ++i) 
  20.         smin[i] = smin[i - 1] + 2 * i * i,
  21.         vmin[i] = vmin[i - 1] + i * i * i;
  22.     pr[M + 1] = ph[M + 1] = INF;
  23. }
  25. void dfs(LL cnt, LL V, LL S) {
  26.     if(cnt < 1) {
  27.         if(V == N) ans = min(ans, S);
  28.         return;
  29.     }
  30.     if(vmin[cnt] + V > N) return;
  31.     if(S + smin[cnt] > ans) return;
  32.     if(2 * (N - V) / pr[cnt + 1] + S > ans) return;
  33.     for(LL r = min((LL)sqrt(1.0 * N - V), pr[cnt + 1] - 1) ; r >= cnt; --r) {
  34.         for(LL h = min((N - V - vmin[cnt - 1]) / r / r, ph[cnt + 1] - 1); h >= cnt; --h) {
  35.             pr[cnt] = r, ph[cnt] = h;
  36.             if(cnt == M) S = r * r;
  37.             dfs(cnt - 1, V + r * r * h, S + 2 * r * h);
  38.         }
  39.     }
  40. }
  42. int main() {
  43.     cin>>N>>M;
  44.     preope();
  45.     dfs(M, 0, 0);
  46.     if(ans == INF) return puts("0"), 0;
  47.     cout<<ans<<endl;
  48.     return 0;
  49. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注