Submission #75708360

---

Source Code Expand

#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)

using namespace std;
const int N=35,M=1500;
int T,n,a[N],len[N],s[N][1700],f[1700][1700],dp[1700],ndp[1700];

void solve(){
    cin>>n;rep(i,1,n){
        cin>>a[i];len[i]=0;int x=a[i];
        while(x)s[i][++len[i]]=x&1,x>>=1;
        rep(j,len[i]+1,1510)s[i][j]=0;
    }
    rep(k,0,M)dp[k]=len[1]+k;
    rep(i,2,n){
        rep(u,1,len[i-1]+M)rep(v,1,len[i]+M)f[u][v]=s[i-1][u]==s[i][v]?f[u-1][v-1]+1:max(f[u-1][v],f[u][v-1]);
        rep(k,0,M){ndp[k]=INF;rep(kp,0,M)ndp[k]=min(ndp[k],dp[kp]+len[i]+k-f[len[i-1]+kp][len[i]+k]);}
        rep(k,0,M)dp[k]=ndp[k];
    }
    int ans=INF;rep(k,0,M)ans=min(ans,dp[k]);cout<<ans<<"\n";
    return;
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>T;while(T--)solve();
    return 0;
}

Submission Info

Judge Result