BZOJ 1111 - [POI2007]四进制的天平Wag

#动态规划 #进制
Published on 2016-09-19

题目地址

描述

Mary 准备举办一个聚会，她准备邀请很多的人参加她的聚会。并且她准备给每位来宾准备一些金子作为礼物。为了不伤及每个人的脸面，每个人获得的金子必须相同。Mary 将要用一个天平来称量出金子。她有很多的砝码，所有砝码的质量都是 4 的幂。Mary 将金子置于左边并且将砝码置于右盘或者两个盘。她希望每次称量都使用最少的砝码。并且，他希望，每次都用不同的称量方法称出相同质量的金子。对于给定的质量 n(n≤101000)n(n\le {10}^{1000})，Mary 希望知道最少需要用多少个砝码可以完成称量，并且想知道用这么多个砝码一共有多少种方式进行称量。

分析

将 nn 转换为四进制，则我们发现，一种可行的方案是将金子放在左边，砝码全部放在右边，这样需要的砝码个数是 v4(n)v_4(n)，即 nn 的四进制表示中各位数的和。但是左盘是可以放砝码的，如果 n=(0003)4n = (0003)_4，将砝码全部放在右边要 3 个。还可以一个 414^1 放在右边，一个 404^0 放在左边，这样就只需要两个砝码，更优。

可以发现一些结论，如果 ，则：

  1. 最大使用到砝码 4m4^m。
  2. 每位最多退位一位（意思是将一个大 4x4^x 的换成 4 个 4x−14^{x - 1}）

可发现，每一位的情况由高一位是否退位决定，如果 ii 位退位，那么 i−1i - 1 位的砝码放在左盘，放置 4−bi−14 - b_{i - 1} 个，这是一个明显的 DP 模型。
设 dp[i][j]dp[i][j] 为处理到前 ii 位，jj 表示 i+1i + 1 位是否退位的最小答案。

当 i+2i + 2 位退位，那么 i+1i + 1 位如果要退位的话，花销反而减小！所以这也是 dp[i+1][1]−1dp[i + 1][1] - 1 的来源。

实现起来有三个技巧，一是转换四进制，先转二进制，然后二进制转四进制，这样就比较方便。二是用 pair<int, int> 来表示答案和方案，用 tension 函数来更新。三是最前最后各加一个 0，这样最优答案就是 dp[0][0]dp[0][0]。

转换四进制的复杂度： O(nlogn)O(n\log n)，DP 的复杂度：O(n)O(n)。

代码

//  Created by Sengxian on 09/19/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 1111 DP
#include <bits/stdc++.h>
using namespace std;

const int MAX_DIGIT = 1000 + 3, INF = 0x3f3f3f3f, modu = 1000000000;
char digits[MAX_DIGIT];
int n, m, bits[MAX_DIGIT * 10];

void convert() {
    int len = n;
    while (len) {
        bits[m++] = digits[0] & 1;
        bool flag = false, tmp = false;
        for (int i = len - 1; i >= 0; --i) {
            tmp = digits[i] & 1;
            digits[i] = (flag * 10 + digits[i]) >> 1;
            flag = tmp;
        }
        if (digits[len - 1] == 0) len--;
    }
    static int tmp[MAX_DIGIT * 10];
    int _m = 0;
    tmp[_m++] = 0;
    for (int i = 0; i < m; i += 2)
        tmp[_m++] = (bits[i + 1] << 1) + bits[i];
    m = _m;
    memcpy(bits, tmp, sizeof bits);
}

inline void tension(pair<int, int> &a, const pair<int, int> &b) {
    if (b.first < a.first) a = b;
    else if (b.first == a.first) (a.second += b.second) %= modu;
}

inline pair<int, int> add(const pair<int, int> &a, const int &b) {           
    return make_pair(a.first + b, a.second);
}

pair<int, int> dp[MAX_DIGIT * 2][2];
void solve() {
    memset(dp, 0x3f, sizeof dp);
    dp[m][0] = make_pair(0, 1);
    for (int i = m; i - 1 >= 0; --i) {
        tension(dp[i - 1][0], add(dp[i][0], bits[i - 1]));
        tension(dp[i - 1][0], add(dp[i][1], bits[i - 1]));
        tension(dp[i - 1][1], add(dp[i][0], 1 + 4 - bits[i - 1]));
        tension(dp[i - 1][1], add(dp[i][1], -1 + 4 - bits[i - 1])); //如果 i + 1 退位了，那么 i 多一个反而要 -1!
    }
    printf("%d\n", dp[0][0].second);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
#endif
    scanf("%s", digits);
    n = strlen(digits);
    if (n == 1 && digits[0] == '0') return puts("1"), 0;
    for (int i = 0; i < n; ++i) digits[i] -= '0';
    reverse(digits, digits + n);
    convert();
    solve();
    return 0;
}
BZOJ 1119 - [POI2009]SLO