# 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

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],  and . 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[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;

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]=0;

}

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

{

dp[i]=ineff[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;

}