dp之双dp前后互补加类二进制均摊思想：SS221109D

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162037356

https://cplusoj.com/d/senior/p/SS221109D

首先可以推一下性质，不难发现，一个数只会进行如此变换：

• 先除至多 $\log_2(n)$ 次

• 再乘至多 $n$ 次

所以一个明显的dp是可以设计的： $f(i,x,y)$ 表示第 $i$ 个位置先除 $x$ 次，再除 $y$ 次的方案数。

转移过程中枚举 $x'$ ，则 $y'$ 的变化可以通过 two-pointer 来实现。

复杂度 $O(n^3\log^2n)$

---

我们考虑优化。

以下是思考过程：

由于初始的数基本比较小，考虑如果它们均大于 $2^{17}$ 时如何处理。

我们再考虑到，由于每个数初始的前缀只有 $\log_2(n)$ 种，我们就可以以这少数的几种，在后面添加0。

而我们可能可以让后面整体某段来乘 $2$ 之类的进行iaoz。

因此，我们可以设 $num(x,y),cnt(x,y)$ 表示对 $x$ 先除 $y$ 次2，再乘至第一次大于等于 $2^{17}$ 得到的值和相应的步数

然后我们再设 $DP(i,j)$ 表示第 $i$ 个数先除 $j$ ， 从第 $i + 1\to n$ 这些数里，有多少步才能满足条件

因为我们需要枚举第 $i+1$ 位，它先除了 $k$

分两种情况讨论：

• $num(i,j) \le num(i +1,k)$

  $$DP(i,j)=DP(i+1,k)+cnt(i,j)$$

• 否则，我则需要让后面所有数都乘个2才行

  $$DP(i,j)=DP(i+1,k)+cnt(i,j)+2(n-i)$$

最后，我们把 $f$ 和 $DP$ 合并即可

---

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
#endif
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 100100
#define X 18
#define Y 36
int n, m, i, j, k, T;
int f[X + 3][Y + 3], g[X + 3][Y + 3], mx, a[N], x, y, z, w, l, r, ans; 
int dp[N][X], cot; 
int num[N][X], cnt[N][X]; 

signed main()
{
	#ifdef LOCAL
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
	
	#ifndef LOCAL
		freopen("sequence.in", "r", stdin);
	  freopen("sequence.out", "w", stdout);
	#endif
//	srand(time(NULL));
	T = read(); read(); 
	while(T--) {
		n = read();  ans = 0; 
		memset(f, 0x3f, sizeof(f)); 
		memset(g, 0x3f, sizeof(g)); 
		memset(dp, 0x3f, sizeof(dp)); 
		memset(num, 0x3f, sizeof(dp)); 
		memset(cnt, 0x3f, sizeof(dp)); 
		for(i = 1; i <= n; ++i) {
			a[i] = read(); 
			int ax = a[i]; cot = 0; 
			while(ax) ax /= 2, ++ans; 
			ax = a[i]; while(ax < (1ll << 17)) ax <<= 1, ++cot; 
			for(j = 0; j <= 17; ++j) {
				num[i][j] = ((a[i] >> j) << (j + cot)), cnt[i][j] = 2 * j + cot;
				if(!num[i][j]) num[i][j] = num[i][j - 1];  
			}
		}
		for(i = n; i >= 1; --i) {
			for(j = 0; j <= 17; ++j) {
				if(i == n) {
					dp[i][j] = cnt[i][j]; continue; 
				}
				for(k = 0; k <= 17; ++k) {
					if(num[i][j] <= num[i + 1][k]) 
						dp[i][j] = min(dp[i][j], dp[i + 1][k] + cnt[i][j]); 
					else dp[i][j] = min(dp[i][j], dp[i + 1][k] + cnt[i][j] + n - i); 
				}
				if(i == 1) ans = min(ans, dp[i][j]); 	
			}
		}
		f[0][0] = 0; mx = f[0][1]; 
		for(i = 1; i <= n; ++i) {
			for(x = 0; x <= 17; ++x)
				for(y = 0; y <= Y; ++y) {
					if(f[x][y] == mx) continue; 
					l = (a[i - 1] >> x) << y; 
					if(l >= (1ll << 17)) break; 
					for(j = 0; j <= 17; ++j)
						if(l <= num[i][j]) 
							ans = min(ans, f[x][y] + dp[i][j]); 
					for(z = 17, w = 34; z >= 0; --z) {
						while(w && ((a[i] >> z) << (w - 1)) >= l) --w; 
						r = (a[i] >> z) << w; 
						if(r >= (1ll << 17)) continue; 
						if(r < l) continue; 
						g[z][w] = min(g[z][w], f[x][y] + z + w); 
						if(i == n) ans = min(ans, g[z][w]); 
					}
				}
			for(x = 0; x <= X; ++x) for(y = 0; y <= Y; ++y) f[x][y] = g[x][y], g[x][y] = mx; 
		}
		printf("%lld\n", ans); 
	}

	return 0;
}