# Untitled

unknown
plain_text
a month ago
2.1 kB
1
Indexable
Never
```#include<bits/stdc++.h>
using namespace  std;
#define int long long
int sm(int i,int j,int *prf)
{
if (i>j)return 0;
if (i==0)return prf[j];
return prf[j]-prf[i-1];
}
int n,k;
vector<vector<int>>dp(100,vector<int>(100,-1));
int rec(int i,int distinct,const vector<vector<int>>&cost,const vector<int>&v)
{
if (i>=n)
{
return 1e18+5;
}
if (dp[i][distinct]!=-1)
return dp[i][distinct];
if (distinct==1)
{
return dp[i][distinct]=cost[i][n-1];
}
if (v[i]<=distinct)
{
return dp[i][distinct]=0;
}
int ans=1e18+5;
for (int j=i;j<=n-1;j++)
{
ans=min(ans,cost[i][j]+rec(j+1,distinct-1,cost,v));
}
return dp[i][distinct]=ans;
}
void solve()
{
cin>>n>>k;
vector<int>a(n);
for (auto &x:a)cin>>x;
dp=vector<vector<int>>(n+5,vector<int>(n+5,-1));
sort(a.begin(),a.end());
int prf[n];
prf[0]=1;
for (int i=1;i<n;++i)
prf[i]=prf[i-1]+a[i];
vector<vector<int>>cost(n,vector<int>(n,1e18));
for (int i=0;i<n;++i)
{
for(int j=i;j<n;j++)
{
if (j==i)
{
cost[i][i]=0;
}
else
{
for (int l=i;l<=j;l++)
{
int nb=max(l-1-i+1,0ll);
int nb1=max(j-(l+1)+1,0ll);
int c1=nb*a[l]-sm(i,l-1,prf);
int c2=sm(l+1,j,prf)-nb1*a[l];
c2=max(c2,0ll);
c1=max(c1,0ll);
cost[i][j]=min(cost[i][j],c1+c2);
}
}
}
}
vector<int>v(n);
set<int>s;
for (int i=n-1;i>=0;i--)
{
s.insert(a[i]);
v[i]=s.size();
}
for (int distinct=1;distinct<=n;distinct++)
{
int r=rec(0,distinct,cost,v);
if (r<=k)
{
cout<<distinct<<'\n';
return;
}
}
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--)solve();
}```