bzoj 1111

Description

给定 1000的十进制数, 求 最小的 四幂拆分 方案 有多少种

Solution

先大除法 (nlog_4(n))次取余转化为 四进制数.
然后从 低位 往 高位 (dp) .
记 (f[i]) 表示不往上借位的最小代价.
(g[i]) 表示往上借位的最小代价(被借的位的代价先不计算).
那么最后答案为 (f[n]+(g[n]+1)) (可以往更高位再借 (1)).

转移为
(f[i] = min(f[i-1] + a[i], g[i-1] + a[i] + 1))
(g[i] = min(f[i-1] + 4 - a[i], g[i - 1] + 3 - a[i]))

边界为
先去掉最低位的所有 (0) , 然后 (f=0,g=inf).

因为要求方案, 所以在 (f,g) 维护二元组 ((cost.ways)) 即可

Code

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <cassert>
#define rep(i, a, b) for (int i = (a); i <= (b); ++ i)
#define per(i, a, b) for (int i = (a); i >= (b); -- i)
#define For(i, a, b) for (int i = (a); i < (b); ++ i)
#define foreach(it, c) for (__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++ it)
#define fore(e, x, y) for (int ep = e(x), y = e[ep].y; ep; y = e[ep = e[ep].nxt].y)
using namespace std;
const int N = 1e3 + 7;
const int M = 2e3 + 7;
const int INF = 1e9 + 7;
const int Mod = 1e9;
 
inline int pls(int x, int y) {return (x + y) % Mod;}
inline int mns(int x, int y) {return pls(x, Mod - y);}
inline int mul(int x, int y) {return 1LL * x * y % Mod;}
inline int Add(int &x, int y) {return x = pls(x, y);}
 
int n, m;
char s[N];
int b[N], a[M];
 
struct rec {
    int cost, ways;
 
    inline rec operator + (const rec &v) {
        if (cost == v.cost) {return (rec){cost, pls(ways, v.ways)};}
        else return cost < v.cost ? *this : v;
    }
 
    inline rec operator + (const int d) const {
        return (rec){cost + d, ways};
    }
}f[M], g[M];
 
int main() {
#ifndef ONLINE_JUDGE
    freopen("a.in", "r", stdin);
#endif
 
    scanf("%s", s+1);
    n = strlen(s+1);
 
    rep (i, 1, n) b[i] = s[i] - '0';
    reverse(b+1, b+n+1);
     
    while (n > 0) {
        int res = 0;
        per (i, n, 1) {
            int d = res * 10 + b[i];
            b[i] = d / 4;
            res = d % 4;
        }
        while (n > 0 && b[n] == 0) --n;
        a[++m] = res;
    }
 
    int bg;
    rep (i, 1, m) if (a[i] != 0) {bg = i; break;}
 
    f[bg - 1] = (rec){0, 1}; g[bg - 1] = (rec){INF, 0};
    rep (i, bg, m + 1) {
        f[i] = (f[i - 1] + a[i]) + (g[i - 1] + (a[i] + 1));
        g[i] = (f[i - 1] + (4 - a[i])) + (g[i - 1] + (3 - a[i]));
    }
 
    printf("%d
", f[m + 1].ways);
 
    return 0;
}