Atcoder CADDi2018 E.Negative Doubling

12月23

Atcoder CADDi2018 E.Negative Doubling

题目描述

给出n个正整数，你可以每次对一个数乘-2，问最少多少次操作能使这些数单调递增。

题解

显然应该让这些数先是一些负数，然后是一些正数，那么问题变成选一个位置，前面的数先乘-2，然后让前面的数单调递减，后面的数单调递增。将顺序颠倒后，前面和后面的解决方法相同。
先考虑后面部分的解决方法，可以发现，一个位置的操作次数超过15，那么每次再对这个位置操作，就要对后面的所有位置操作。
定义f[i][j]表示考虑i-n的数，对i位置上操作j次后满足条件的需要操作的最少次数，然后转移即可。
之后枚举分界点求答案。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int read()
{
    char ch=getchar();int f=0,x=1;
    while(ch<'0'||ch>'9'){if(ch=='-') x=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){f=(f<<1)+(f<<3)+ch-'0';ch=getchar();}
    return f*x;
}
ll f[200005][19],g[200005][19];
int n;ll a[200005],pow1[17];
const ll inf=1000000000000000000LL;
int main()
{
    //freopen("1.in","r",stdin);
    memset(f,0x3f3f3f3f,sizeof(f));
    memset(g,0x3f3f3f3f,sizeof(g));
    for(int i=0;i<=n+1;i++)
    {
        for(int j=0;j<=15;j++)
        f[i][j]=g[i][j]=inf;
    }
    n=read();
    pow1[0]=1;
    for(int i=1;i<=15;i++) pow1[i]=pow1[i-1]*4;
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    for(int i=0;i<=15;i++) f[1][i]=i;
    for(int i=2;i<=n;i++)
    {
        for(int j=0;j<=15;j++)
        {
            for(int k=15;k>=0;k--)
            {
                if(a[i-1]*pow1[k]>=a[i]*pow1[j])
                {
                    f[i][j]=min(f[i][j],f[i-1][k]+j);
                }
            }
            if(f[i][j]==4557430888798830399LL) f[i][j]=f[i][j-1]+i;
        }
    }
    for(int i=0;i<=15;i++) g[n][i]=i;
    for(int i=n-1;i;i--)
    {
        for(int j=0;j<=15;j++)
        {
            for(int k=15;k>=0;k--)
            {
                if(a[i+1]*pow1[k]>=a[i]*pow1[j])
                {
                    g[i][j]=min(g[i][j],g[i+1][k]+j);
                }
            }
            if(g[i][j]==4557430888798830399LL) g[i][j]=g[i][j-1]+(n-i+1);
        }
    }
    ll ans=inf;
    f[0][0]=g[0][0]=f[n+1][0]=g[n+1][0]=0;
    for(int i=0;i<=n;i++)
    {
        ll num1,num2;num1=num2=inf;
        for(int j=0;j<=15;j++)
        {
            num1=min(num1,f[i][j]);
            num2=min(num2,g[i+1][j]);
        }
        ans=min(ans,1LL*num1*2+1LL*num2*2+1LL*i);
    }
    cout<<ans;
}

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

int read()

{

char ch=getchar();int f=0,x=1;

while(ch<'0'||ch>'9'){if(ch=='-') x=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){f=(f<<1)+(f<<3)+ch-'0';ch=getchar();}

return f*x;

}

ll f[200005][19],g[200005][19];

int n;ll a[200005],pow1[17];

const ll inf=1000000000000000000LL;

int main()

{

//freopen("1.in","r",stdin);

memset(f,0x3f3f3f3f,sizeof(f));

memset(g,0x3f3f3f3f,sizeof(g));

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

{

for(int j=0;j<=15;j++)

f[i][j]=g[i][j]=inf;

}

n=read();

pow1[0]=1;

for(int i=1;i<=15;i++) pow1[i]=pow1[i-1]*4;

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

{

a[i]=read();

}

for(int i=0;i<=15;i++) f[1][i]=i;

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

{

for(int j=0;j<=15;j++)

{

for(int k=15;k>=0;k--)

{

if(a[i-1]*pow1[k]>=a[i]*pow1[j])

{

f[i][j]=min(f[i][j],f[i-1][k]+j);

}

if(f[i][j]==4557430888798830399LL) f[i][j]=f[i][j-1]+i;

}

for(int i=0;i<=15;i++) g[n][i]=i;

for(int i=n-1;i;i--)

{

for(int j=0;j<=15;j++)

{

for(int k=15;k>=0;k--)

{

if(a[i+1]*pow1[k]>=a[i]*pow1[j])

{

g[i][j]=min(g[i][j],g[i+1][k]+j);

}

if(g[i][j]==4557430888798830399LL) g[i][j]=g[i][j-1]+(n-i+1);

}

ll ans=inf;

f[0][0]=g[0][0]=f[n+1][0]=g[n+1][0]=0;

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

{

ll num1,num2;num1=num2=inf;

for(int j=0;j<=15;j++)

{

num1=min(num1,f[i][j]);

num2=min(num2,g[i+1][j]);

}

ans=min(ans,1LL*num1*2+1LL*num2*2+1LL*i);

}

cout<<ans;

}

mengbierr