Chef and Wedding Arrangements | Solutions CHEFWED

Chef and Wedding Arrangements SOLUTION

There are N visitors (numbered 1 through N) going to Chef’s wedding. Every visitor is important for a family; for each substantial I, the I-th visitor is essential for family Fi. You have to assist Chef with finding an ideal guest plan. 

Culinary specialist may purchase various tables, which are huge enough for quite a few visitors, however the individuals sitting at each table must have successive numbers ― for any two visitors I and j (i<j) sitting at a similar table, visitors i+1,i+2,… ,j−1 should likewise sit at that table. Gourmet specialist would have gotten a kick out of the chance to situate all visitors at a solitary table; nonetheless, he saw that two visitors I and j are probably going to get into a contention if Fi=Fj and they are sitting at a similar table. 

Each table costs K rupees. Gourmet specialist characterizes the shortcoming of a guest plan as the all out expense of tables in addition to the quantity of visitors who are probably going to get into a contention with another visitor. Disclose to Chef the base conceivable shortcoming which he can accomplish. 

 

Info 

The main line of the information contains a solitary number T meaning the quantity of experiments. The portrayal of T experiments follows. 

The principal line of each experiment contains two space-isolated numbers N and K. 

The subsequent line contains N space-isolated whole numbers F1,F2,… ,FN. 

Yield For each experiment, print a solitary line containing one whole number ― the littlest conceivable shortcoming. 

 

Requirements 

1≤T≤100 

1≤N≤1,000 

1≤K≤1,000 

1≤Fi≤100 for each legitimate I 

The entirety of N across experiments is ≤5,000 

 

Subtasks 

Subtask #1 (20 focuses): K=1 

Subtask #2 (80 focuses): unique imperatives 

 

Model Input 

5 1 

5 1 3 

5 14 

1 4 2 4 

5 2 

3 5 4 5 1 

 

Model Output 

17 

 

Clarification 

Model case 1: The ideal arrangement is to utilize three tables with gatherings of visitors [1,2,3], [4] and [5]. None of the tables have any visitors that are probably going to get into a contention, so the failure is 3⋅K=3. 

Model case 2: The ideal arrangement is to situate all visitors at one table. At that point, visitors 2, 4 and 5 are probably going to get into a contention with one another, so the failure is K+3=17.

 

Solution

CODE C++14 :

#include<bits/stdc++.h>

#define ll long long

#define Amax 1e18

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)

using namespace std;

int main()

{

    fastio;

    ll i,j,k,s,T,N,K;

    cin>>T;

    while(T–)

    {

        cin>>N>>K;

        ll A[N+1], ans=Amax, fmin=Amax;

        ll ineff[N+1][N+1];

        ll dp[101][N+1];

        for(i=0;i<N+1;i++)

        {

            for(j=0;j<N+1;j++)

            {

                ineff[i][j]=0;

            }

        }

        for(i=0;i<101;i++)

        {

            for(j=0;j<N+1;j++)

            {

                dp[i][j]=0;

            }

        }

        for(i=0;i<N;i++)

        {

            cin>>A[i];

        }

        for(i=0;i<N;i++)

        {

            unordered_map<ll,ll> m;

            ineff[i][0]=0;

            for(j=i;j<N;j++)

            {

                if(j>0)

                {

                    ineff[i][j]=ineff[i][j-1];

                }

                m[A[j]]++;

                if(m[A[j]]==2)

                {

                    ineff[i][j]+=2;

                }

                else if(m[A[j]]>2)

                {

                    ineff[i][j]++;

                }

            }

        }

        for(i=2;i<101;i++)

        {

            dp[i][1]=0;

        }

        for(i=1;i<N+1;i++)

        {

            dp[1][i]=ineff[0][i-1];

        }

 

        for(i=2;i<101;i++)

        {

            for(j=2;j<N+1;j++)

            {

                fmin=Amax;

                for(k=1;k<j;k++)

                {

                    fmin=min(fmin,dp[i-1][k]+ineff[k][j-1]);

                }

                dp[i][j]=fmin;

            }

        }

        for(i=1;i<101;i++)

        {

            ans=min(i*K+dp[i][N],ans);

        }

        cout<<ans<<endl;

    }

    return 0;

}

Leave a Comment