Problem B
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 59 Accepted Submission(s) : 27
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
Given three arraies A[],B[],C[], each contains N non-negative integers.You are asked to maxmize the vale:V=max(A[i]+B[j]+C[k]), where 0<i,j,k<=N and i!=j and j!=k and i!=k.
Input
Each case contains 4 lines,
the first line contains an integer N( 3<=N<=10000 ) ,
the second line contains N integers representing array A[],
the third line contains N integers representing array B[],
the fourth line contains N integers representing array C[].
the first line contains an integer N( 3<=N<=10000 ) ,
the second line contains N integers representing array A[],
the third line contains N integers representing array B[],
the fourth line contains N integers representing array C[].
Output
Each case contains a number seperately: the answer V.
Sample Input
3
1 2 3
3 2 1
3 2 1
Sample Output
8
思路：
int dfs(int i,int j,int k)
{
if(A[i].pos!=B[j].pos&&A[i].pos!=C[k].pos&&B[j].pos!=C[k].pos)
return A[i].l+B[j].l+C[k].l;
if(A[i].pos==B[j].pos)
return max(dfs(i+1,j,k),dfs(i,j+1,k));
if(A[i].pos==C[k].pos)
return max(dfs(i+1,j,k),dfs(i,j,k+1));
if(C[k].pos==B[j].pos)
return max(dfs(i,j+1,k),dfs(i,j,k+1));
}
{
if(A[i].pos!=B[j].pos&&A[i].pos!=C[k].pos&&B[j].pos!=C[k].pos)
return A[i].l+B[j].l+C[k].l;
if(A[i].pos==B[j].pos)
return max(dfs(i+1,j,k),dfs(i,j+1,k));
if(A[i].pos==C[k].pos)
return max(dfs(i+1,j,k),dfs(i,j,k+1));
if(C[k].pos==B[j].pos)
return max(dfs(i,j+1,k),dfs(i,j,k+1));
}
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
using namespace std;
struct node
{
int l;int pos;
};
node A[10001],B[10001],C[10001];
int N;
int cmp(const void *i,const void *j)
{
node *ii=(node *)i,*jj=(node *)j;
return jj->l-ii->l;
}
void input()
{
for(int i=1;i<=N;i++)
{
scanf("%d",&A[i].l);
A[i].pos=i;
}
for(int i=1;i<=N;i++)
{
scanf("%d",&B[i].l);
B[i].pos=i;
}
for(int i=1;i<=N;i++)
{
scanf("%d",&C[i].l);
C[i].pos=i;
}
qsort(A+1,N,sizeof(A[1]),cmp);
qsort(B+1,N,sizeof(A[1]),cmp);
qsort(C+1,N,sizeof(A[1]),cmp);
}
int dfs(int i,int j,int k)
{
if(A[i].pos!=B[j].pos&&A[i].pos!=C[k].pos&&B[j].pos!=C[k].pos)
return A[i].l+B[j].l+C[k].l;
if(A[i].pos==B[j].pos)
return max(dfs(i+1,j,k),dfs(i,j+1,k));
if(A[i].pos==C[k].pos)
return max(dfs(i+1,j,k),dfs(i,j,k+1));
if(C[k].pos==B[j].pos)
return max(dfs(i,j+1,k),dfs(i,j,k+1));
}
void solve()
{
int ans=dfs(1,1,1);
printf("%d\n",ans);
}
int main()
{
while(cin>>N)
{
input();
solve();
}
}