HDU 5798 Stabilization

方法太厉害了....看了官方题解的做法....然后...想了很久很久才知道他想表达什么....

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<iostream>

using namespace std;

typedef long long LL;

const double pi=acos(-1.0),eps=1e-;

void File()

{

    freopen("D:\\in.txt","r",stdin);

    freopen("D:\\out.txt","w",stdout);

}

inline int read()

{

    char c = getchar();  while(!isdigit(c)) c = getchar();

    int x = ;

    while(isdigit(c)) { x = x *  + c - ''; c = getchar(); }

    return x;

}

int T,n;

LL a[],f[][],ans1,ans2;

int d[];

void dfs(int s,LL b, LL sum)

{

    if(s==-)

    {

        if(sum<ans1) ans1=sum,ans2=b;

        else if(sum==ans1) ans2=min(ans2,b);

        return;

    }

    for(d[s]=;d[s]<=;d[s]++)

    {

        LL t=sum; t=t+f[s][s];

        for(int j=;j>s;j--)

        {

            if((d[j]+d[s])%==) t=t+f[j][s];

            else t=t-f[j][s];

        }

        dfs(s-,b|(d[s]*(<<s)),t);

    }

}

int main()

{

    scanf("%d",&T); while(T--)

    {

        scanf("%d",&n);

        for(int i=;i<=n;i++) scanf("%lld",&a[i]);

        memset(f,,sizeof f); ans1=, ans2=;

        for(int i=;i<=n;i++)

        {

            ans1=ans1+abs(a[i]-a[i-]);

            if(a[i]==a[i-]) continue;

            int h=-;

            for(int j=;j>=;j--)

            {

                int x1=,x2=;

                if(a[i]&(<<j)) x1=; if(a[i-]&(<<j)) x2=;

                if(x1==x2) continue; h=j; break;

            }

            int x=max(a[i],a[i-]),y=min(a[i],a[i-]);

            for(int j=h;j>=;j--)

            {

                int x1=,x2=;

                if(x&(<<j)) x1=; if(y&(<<j)) x2=;

                f[h][j]=f[h][j]+(x1-x2)*(<<j);

            }

        }

        dfs(,,);

        printf("%lld %lld\n",ans2,ans1);

    }

    return ;

}