将一个数组分成三部分（递归）

Question

问题Link：

https://www.hackerearth.com/problem/algorithm/divide-to-three-33/description/

我能够使用动态规划来解决它。 https://www.hackerearth.com/submission/1720148/

谁能给我解释一下编辑解决方案（递归）。

编辑解决方案：

#include<cstdio>
#include<cstdio>
#include<queue>
#include<cstring>
#include<vector>
#include<iostream>
#include<string>
#include<algorithm>
#include<fstream>
#include<sstream>
using namespace std;
typedef long long int int64;
int64 n,a[40],ans,vl;
void fn(int64 i,int64 j,int64 k,int64 ptr){
    if(ptr==n){
        vl = max(max(i,j),k);if(vl<ans)ans=vl;
    }
    else{
        fn(i+a[ptr],j,k,ptr+1);
        fn(i,j+a[ptr],k,ptr+1);
        fn(i,j,k+a[ptr],ptr+1); 
    }
}
int main(){
//freopen("in3.txt","r",stdin);
//freopen("out3.txt","w",stdout);
    int64 i,j,k,l,m,t,vl,fl;ans=1000000;
    cin>>n;for(i=0;i<n;i++)cin>>a[i];
    fn(0,0,0,0);
    printf("%lld\n",ans);

    return 0;
}

谢谢，

Answer 1

思路很简单，三组（S1 or S2 or S3）中的任意一个都可以加一个元素。使用函数 fn，编码器正在对一个表示为 ny ptr 的元素执行 basically.Look（元素为 a[ptr]），它要么被添加到 first(i) ，第二个（j）或最后一个（k）。其中最大值作为输出给出。

实际上，这三行检查了向三个集合中的任何一个添加元素的所有可能性

    fn(i+a[ptr],j,k,ptr+1);
    fn(i,j+a[ptr],k,ptr+1);
    fn(i,j,k+a[ptr],ptr+1);

基本条件显然是当我们检查完数组中的所有元素时

if(ptr==n){
    vl = max(max(i,j),k);if(vl<ans)ans=vl;
    }

the maximum of three set sums are found in max(max(i,j),k).

Now if(vl<min) will determine the minimum S1 satisfying the condition. That's why this check is v1<ans, we will try to minimize S1.

Here i,j,k are denoting the sum of the corresponding set.

将一个数组分成三部分（递归）

Divide an array into Three parts (Recursion)

c++

arrays

recursion

dynamic-programming

partition