?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
46674555 |
Practice: luogu_bot4 |
1070J - 29 | GNU C++11 | Accepted | 124 ms | 416 KB | 2018-12-06 12:00:37 | 2018-12-06 12:00:37 |
#include <iostream> #include <cstdio> #include <cstring> #define ll long long #define INF (1ll<<60ll) using namespace std; ll T,m,n,K,dy,cnt[27],ans; char str[200100]; bool dp[200100]; signed main() { register ll i,j,k; scanf("%lld",&T); dp[0]=1; while(T--) { scanf("%lld%lld%lld%s",&m,&n,&K,&str[1]); memset(cnt,0,sizeof cnt); ans=INF; dy=K-m-n; if(m>n)swap(m,n); for(i=1;i<=K;i++)cnt[str[i]-'A'+1]++; for(i=1;i<=26;i++) { for(j=1;j<=n;j++)dp[j]=0; for(j=1;j<=26;j++){if(i==j)continue;for(k=n;k>=cnt[j];k--)dp[k]|=dp[k-cnt[j]];} for(j=min(cnt[i],n);j>=0;j--){if(!dp[n-j])continue; ans=min(ans,j*max(0ll,cnt[i]-j-dy));} } printf("%lld\n",ans); } return 0; }
?
?
?
?