Atcoder CADDi2018 E.Negative Doubling
题目描述
给出n个正整数,你可以每次对一个数乘-2,问最少多少次操作能使这些数单调递增。
题解
显然应该让这些数先是一些负数,然后是一些正数,那么问题变成选一个位置,前面的数先乘-2,然后让前面的数单调递减,后面的数单调递增。将顺序颠倒后,前面和后面的解决方法相同。
先考虑后面部分的解决方法,可以发现,一个位置的操作次数超过15,那么每次再对这个位置操作,就要对后面的所有位置操作。
定义f[i][j]表示考虑i-n的数,对i位置上操作j次后满足条件的需要操作的最少次数,然后转移即可。
之后枚举分界点求答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#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; } |