代码源 每日一题 div1 删数

删数

今天的题又不会写，所以来写题解总结一下

题意

给你一个数组，每次如果 a i = ( a i + 1 + a i − 1 ) / 2 a_i=(a_{i+1}+a_{i-1})/2 ai​=(ai+1​+ai−1​)/2，那么就可以删除 a i a_i ai​。

问这个数组经过一系列删除后最短长度是多少？

思路

注意到，能删除的数字是等差数列中间的那个数字，所以我们可以构造差分数组 d [ i ] = a [ i + 1 ] = a [ i ] d[i] = a[i + 1] = a[i] d[i]=a[i+1]=a[i]，删除 a [ i ] a[i] a[i]后，新的 d [ i ] d[i] d[i]刚好是旧 d [ i ] d[i] d[i]的两倍，即等价于合并两个相同的 d [ i ] d[i] d[i]。

所以，这个问题就转化为，给你一个数组 d d d，每次可以合并相邻且值相同的两个值，问这个数组最后能剩下最少的数字是多少？

因为每次合并都是连续的区间，而且对于 d [ i ] d[i] d[i]所在合并后的区间，其值必定为 d [ i ] ∗ 2 k ( k = 0 , 1 , . . . ) d[i]*2^k (k=0,1,...) d[i]∗2k(k=0,1,...)。

既然到了这里，不妨再进一步处理，把2的因子全部提取出来。

有了上面这个观察，我们再考虑DP，记 d p [ i ] dp[i] dp[i]为合并前i个数字，最后得到最少的数字。

对于每个 d [ i ] d[i] d[i]，我们只需要包含它，且和为 d [ i ] ∗ 2 k d[i]*2^k d[i]∗2k的区间即可。

所以，我们还缺一个数组 f [ i ] [ j ] f[i][j] f[i][j]，表示以i开头，和为 d [ i ] ∗ 2 k d[i]*2^k d[i]∗2k的区间最右边是哪个位置。

到了这一步，很明显 f [ i ] [ j ] f[i][j] f[i][j]可以用倍增的思想处理出来，即 f [ i ] [ j ] = f [ f [ i ] [ j − 1 ] [ j − 1 ] ] f[i][j] = f[f[i][j-1][j - 1]] f[i][j]=f[f[i][j−1][j−1]]。

另外，要注意一点，如果 d [ i ] d[i] d[i]不相等，那么 f [ i ] [ j − 1 ] f[i][j-1] f[i][j−1]不能和 f [ f [ i ] [ j − 1 ] [ j − 1 ] ] f[f[i][j-1][j - 1]] f[f[i][j−1][j−1]]这个位置合并，而且如果 d [ i ] = = 0 d[i]==0 d[i]==0的话，那么可以直接无视其他的条件进行合并。

具体看代码。

最后就是进行dp过程了，因为 f f f是考虑右边的位置，所以dp含义这里改变一下， d p [ i ] dp[i] dp[i]表示从 i i i开始到n，合并后可以得到的最少数字

• 状态转移 d p [ i ] = d p [ f [ i ] [ j ] ] + 1 dp[i] = dp[f[i][j]] + 1 dp[i]=dp[f[i][j]]+1
• 因为我们合并的是差分数组，所以最后答案为 d p [ 1 ] + 1 dp[1]+1 dp[1]+1
• 剩余一些细节可以参考代码

#include 
#define x first
#define y second
using namespace std;
typedef long long LL;
using tp = tuple<int,int,int>;
typedef pair<int,int> PII;
const int N = 3e5 + 10, M = 3010, mod = 998244353, INF = 1e9;
bool multi = true;


int n;
int d[N], a[N], cnt[N];
//第i个位置，合并变成d[i]*2^k，到什么地方
int f[N][55], dp[N];
void solve() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);

    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= 50; j++) f[i][j] = -1;

    n--;
    for(int i = 1; i <= n; i++) {
        d[i] = a[i + 1] - a[i];
        cnt[i] = 0, dp[i] = INF;
        while(d[i] && d[i] % 2 == 0) {
            cnt[i]++;
            d[i] /= 2;
        }
    }
    
    for(int i = n; i >= 1; i--) {
        f[i][cnt[i]] = i + 1;
        for(int j = 1; cnt[i] + j <= 50; j++) {
            if(f[i][cnt[i] + j - 1] > n) break;
            if(f[i][cnt[i] + j - 1] == -1) break;
            if(d[i] != d[f[i][cnt[i] + j - 1]]) break;
            f[i][cnt[i] + j] = f[f[i][cnt[i] + j - 1]][cnt[i] + j - 1];
        }
    }
    dp[n + 1] = 0;
    //i~n，合并后能剩下的最少区间数量
    for(int i = n; i >= 1; i--) {
        if(i + 1 <= n && !d[i] && !d[i + 1]) dp[i] = dp[i + 1];
        else {
            for(int j = 0; j <= 50; j++) {
                if(f[i][j] == -1) continue;
                dp[i] = min(dp[i], dp[f[i][j]] + 1);
            }
        }
    }
    cout << dp[1] + 1 << endl;
    
}

int main() {
    int T = 1;
    if(multi) cin >> T;
    while (T--) solve();
    return 0;
}