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
3
5 1
5 1 3
5 14
1 4 2 4
5 2
3 5 4 5 1
Model Output
3
17
4
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.
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;
}
