algorithm - 想不通这个算法的通用名叫什么？

Question

我刚刚做了一个 Top Coder SRM，其中有一个问题我无法解决。我正在尝试在线搜索该算法的详细信息，但似乎找不到。

问题围绕着以下几行:你有一个数组，例如 [12, 10, 4]

每一轮，您可以应用 9,3,1 的任意排列从 [12,10,4] 中减去

返回数组中所有数字为 0 所需应用的最小排列数。

有什么帮助吗？

编辑:让我更具描述性，以便更好地理解问题。

One question would be
input: [12 10 4]
output: 2 (minimum rounds)

How it would work:
[12 10 4] - [9 3 1] = [3 7 3]
[12 10 4] - [9 1 3] = [3 9 1]
[12 10 4] - [3 9 1] = ..
[12 10 4] - [3 1 9] = ..
[12 10 4] - [1 3 9] =
[12 10 4] - [1 9 3] =

[3 7 3] - [3 9 1] = ...

..
[9 1 3] - [9 1 3] = [0 0 0] <-- achieved with only two permutation subtractions

编辑2:

这是顶级编码器问题: http://community.topcoder.com/stat?c=problem_statement&pm=13782

编辑3:如果有人认为解决方案是动态规划，他们还可以解释重叠子问题和最优子结构吗？

Answer 1

编辑:

在看到原始问题后，这里是为上述问题链接中提供的每个测试用例提供正确输出的解决方案，如果你想输入 {60}，你应该输入 {60,0,0}。

基本思想是，你需要让它们最后都小于或等于零，所以如果数字可以被 3 整除，你可以通过减去 9 或 3 得到零，如果不能整除，减去 1 使它成为能被3整除

首先，对给定的三元组进行排序，然后

• 检查最大的数是否可以被3整除，如果是，减去9仍然可以被3整除
• 现在检查下一个最大的数，如果它能被 3 整除，则减去 3，否则减去 1
• 如果最大数不能被3整除，则减1使其可以被3整除
• 现在将下一个最大的数减去 9，将另一个数减去 3

这里是实现

#include <iostream>
#include <algorithm>
#include<cmath>
using namespace std;
int f(int* a,int k){
sort(a,a+3);
if(a[2]<=0 )
{cout << k<< endl ;
return 0;}

if(a[1]<=0){
cout << k+ceil((double)a[2]/9) << endl;
return 0;

}
if(a[2]%3==0 ){
a[2]=a[2]-9;
if(a[1]%3==0 )
{
    a[1] = a[1] -3;
    a[0] = a[0] -1;
}
else{
    if(a[2]%2==0 && (a[1]-1)%2==0  && a[1]!=0){
        a[2]=a[2] +9 -3;
        a[1] = a[1] -9;
        a[0] = a[0]-1;
    }
    else{
    a[1] = a[1] -1;
    a[0] = a[0] - 3;}
}
return f(a,++k);
}
else{
a[2] = a[2] -1;

    a[1] = a[1] -9;
    a[0]=a[0] -3;
return f(a,++k);

}
}
int main() {

int a[] = {54,18,6};
f(a,0);
return 0;
}

希望对你有帮助

示例:输入是 [12,4,10]

对其进行排序 [12,4,10] -> [12,10,4]

现在检查最大数是否能被3整除，这里是

所以[12-9,10,4] -> [3,10,4]现在检查下一个能被 3 整除的最大数，这里是 N0

所以[3,10-1,4-3] ->[3,9,1]

现在递增计数并将其传递给函数(递归)

输入 -> [3,9,1]

排序 [3,9,1] -> [9,3,1]

现在检查最大数是否能被3整除，这里是

所以 [9-9,3,1] -> [0,3,1]

现在检查下一个能被 3 整除的最大数，这里 Yes

所以 [0,3-3,1-1] -> [0,0,0]

现在递增计数并传递数组

因为最大的元素是 0 ，我们将打印计数，即 2