I have an algorithm problem that I want to solve. I have tried to solve it with dynamic approche but it didn't get all answers right
Coach Fegla suggested the following game: An even number (N) of contestants are chosen and asked to stand in a circle, where each contestant is given an ID. There is a number of ropes. The contestants need to be matched in pairs where each pair carry a rope without any two ropes intersecting. The cost of matching 2 people i and j is (ID[i] + ID[j])2, where ID[i] is the ID of the student standing in position i in the circle. And the cost of the entire circle is the sum of the costs of all pairs.
What is the minimum circle cost to match them in N/2 pairs so that no 2 ropes intersect?
Input The input starts with a single integer T on the first line, denoting how many test-cases are in the input.
Each test-case is given on 2 lines, the first one has a single integer N denoting the number of students in this test-case. The second line consists of N space separated integers, representing the IDs of the students in a clockwise order of their position in the circle.
Output For each test-case print one line that has an integer that is the minimum circle match cost for that test-case.
#include <iostream>
#include <algorithm>
#include <fstream>
#include <cmath>
using namespace std;
int t[201];
int N;
long long int minCout[201][201];
int minimum(int d,int f)
{
if(d>=f)
return 0;
if(minCout[d][f]!=-1)
return minCout[d][f];
long long int coutMin=20000000000000000;
for(int i=d+1;i<=f;i++)
{
if((i-d)%2==1)
{
int curValue=pow(t[d]+t[i],2)+minimum(d+1,i-1)+minimum (i+1,f);
if(curValue<coutMin)
coutMin=curValue;
}
}
minCout[d][f]=coutMin;
return coutMin;
}
int main()
{
ifstream myfile;
myfile.open ("game.in");
int test;
myfile>>test;
for(int i=0;i<test;i++)
{
myfile>>N;
for(int j=0;j<N;j++)
myfile>>t[j];
for(int j=0;j<N;j++)
for(int k=0;k<N;k++)
minCout[j][k]=-1;
cout<<minimum(0,N-1)<<endl;
}
myfile.close();
}
this are the test given to me
input
2
2
1 2
4
1 2 1 2
output
9
18
Can you please help me find an exemple that don't work with my algorithm I have done many exemple in paper and I didn't find an exemple that don't work. Or can you tell me the error in my algorithm and what méthode to use when solving such problem.
Aucun commentaire:
Enregistrer un commentaire