Разделите массив на три части (рекурсия)
Проблема Ссылка:
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;
}
Спасибо,
Решение
Идея очень проста, вы можете добавить элемент к любому из трех наборов (S1 или S2 или S3). Используя функцию fn кодер делает это в основном. Ищите элемент, обозначенный ny ptr (элемент a[ptr]) либо добавляется в первую очередь (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;
}
максимум три установленные суммы находятся в
max(max(i,j),k),Сейчас
if(vl<min)определит минимумS1удовлетворяющее условию. Вот почему эта проверкаv1<ansпостараемся свести к минимумуS1,Здесь i, j, k обозначают сумму соответствующего множества.
Другие решения