dimanche 29 janvier 2017

Game of Circles Algorithm

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