Cubes UVALive - 7708

标签： 搜索

---

题目描述

戳这里
题目大意：给你一个数$n$，要求将$n$分解成$m$个数的立方和，要求$m$最小且输出方案

题解

很容易能想到这道题可以用记忆化搜索，设$f[i]$表示数字为$i$时最少分解次数。然后我们就枚举每个数的三次方，可以发现这个数最大不会超过$356$，然后用当前数$x$减去枚举数的三次方$i\ast i\ast i$作为下一层递归的数字，即为$x-i\ast i\ast i$。当发现$f[x]$的值已经存在时，我们就不用递归往下了，可以记录答案了。
那么本题最重要的剪枝其实就一个：最优性剪枝。
我们每次递归到$f[x]$存在时，就用一个$ans$记录当前已经统计到的答案（不一定最优）,在$dfs$时记录一个参数$cnt$，表示当前已经用了$cnt$次，如果你发现$cnt+x/(i\ast i\ast i)>=ans$,那么就可以直接$break$掉了。
这里要强调的是，判定式必须用$>=$而不是$>$,虽然看似没什么区别，可能后者会计算次数多一点。但打表发现，当数字较大时，它的分解次数其实会很小，一般只有$4$或$5$次，而$cnt$多一次，递归次数会多大概一个数量级的次数，所以这个时间效率我们不能忽视。
eg:
对于$44777444$这个数据，如果判定式用$>$，那么程序大概会跑$4$亿次，而如果换成$>=$，程序只用跑$1600$万次。

代码

#include<bits/stdc++.h>
#define N 46000000
using namespace std;

int n, ass;
int f[N], to[N], wo[N], id[N];

bool cmp(int a, int b) {return a > b;}

int dfs(int x, int y, int fr, int c)
{ 
    if(y > ass) return N;
    if(f[x] != -1) 
    {
        if(ass > y + f[x]) ass = y + f[x];
        return f[x];
    }
    int ans = N, tt, ww, dd;
    if(y + max(1, x / (c * c *c)) >= ass) return N;
    for(int i = c; i >= 1; i --)
    {
        if(i * i * i > x) continue;
        int w = x / (i * i * i);
        if(y + w >= ass) break;
        int t = dfs(x - (i * i * i), y + 1, fr, i) + 1;
        if(ans > t) ans = t, tt = x - (i * i * i), ww = 1, dd = i;
    }
    if(ans != N) f[x] = ans, to[x] = tt, wo[x] = ww, id[x] = dd;
    return ans;
}

int main()
{
    memset(f, -1, sizeof(f));
    memset(to, 0, sizeof(to));
    f[0] = 0; ass = 20;
    for(int i = 1; i <= 356; i ++)
    {
        int x = i * i * i;
        f[x] = 1; to[x] = 0; id[x] = i; wo[x] = 1;
    }
    for(int i = 1; i <= 1e5; i ++)
        ass = 2000, f[i] = dfs(i, 0, i, 356);
    while(scanf("%d", &n) != EOF)
    {
        ass = 2000;
        int ans = dfs(n, 0, n, 356);
        printf("%d\n", ans); 
        int x = n, cnt = 0; 
        int b[20];
        while(x)
        {
            for(int i = cnt; i < cnt + wo[x]; i ++)
                b[i] = id[x];
            cnt += wo[x]; x = to[x]; 
        }
        sort(b, b + cnt, cmp);
        for(int i = 0; i < cnt; i ++) printf("%d ", b[i]);
        printf("\n");
    }
    return 0;
}

心得

有时候往往一个小细节就影响了程序的效率，这主要还是决定于题目的性质，不过我们还是尽量采用高效的方法来写代码，不放过优化的地方。