Untitled
#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(); }
Leave a Comment