Codechef Chef and Wedding Arrangements Problem Code: CHEFWED Solution

 #include <bits/stdc++.h>
using namespace std;
vector<vector<int> > diff;
vector<int> dp;
int n,K,cost;
int rec(int i){
    if(dp[i]!=-1)return dp[i];
    int mn=int(1e9),idx=-1,tcost;
    for(int j=i;j<n;j++){
        if(diff[i][j]+diff[j+1][n]+K<=diff[i][n]){
            tcost=diff[i][j]+K+rec(j+1);
            if(tcost<mn){mn=tcost,idx=j;}
        }
    }
    return dp[i]=min(mn,diff[i][n]);
}
int main()
{     
    int t;
    cin>>t;
    while(t--){
        cin>>n>>K;
        diff.assign(n+1,vector<int>(n+1,0));
        dp.assign(n+1,-1);
        cost=K;
        vector<int> f(n+1);
        for(int i=1;i<=n;i++)
            cin>>f[i];
        for(int i=1;i<=n;i++){        
        map<int,int> m;
        int d=0;
            for(int j=i;j<=n;j++){
                m[f[j]]++;
                if(m[f[j]]==2)d+=2;
                else if(m[f[j]]>2) d+=1;
                diff[i][j]=d;
            }
        }
        
        cout<<rec(1)+K<<'\n';
    }
    return 0;
}