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

本文主要是介绍BZOJ 1111: [POI2007]四进制的天平Wag，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1111: [POI2007]四进制的天平Wag

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 223 Solved: 151
[Submit][Status][Discuss]

Description

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

Input

输入文件仅包含一个整数，表示Mary希望给每个人的金子的质量。（1<=n<=10^1000）

Output

输出文件仅包含一个整数，表示一共可能的称量方式对10^9的模。

Sample Input

166

Sample Output

3
样例解释
一共有三种方式称量出166。166=64+64+16+16+4+1+1。166=256-64-16-16+4+1+1。166=256-64-16-4-4-1-1。

HINT

Source

[ Submit][ Status][ Discuss]

分析

讲真，这题动态规划的思路不难，上了趟WC就有了，但是废了好大劲才把这个巨型整数变成4进制，当然中间是“天马行空”就是了。

假如已经有了这个整数的四进制表示方法，如166的四进制数2212，称第1个2为第1位，第2个2为第2位，而1为第3位。

动态规划如下：

F[i][0]表示第i位上目前就是第i位数字的最小操作数。

F[i][1]表示第i位上目前是第i位数字+1的最小操作数。

G[i][0]和G[i][1]分别对应两者的方案数。

对于F数组，有如下转移——

F[i][0] <- F[i - 1][0] + num[i]
F[i][0] <- F[i - 1][1] + 4 - num[i]
F[i][1] <- F[i - 1][0] + num[i] - 1
F[i][1] <- F[i - 1][1] + 3 - num[i]

显然就是枚举达到当前转态要求的数字，可以用什么方式得到。要么是从0加到num[i]，要么是从4减到num[i]。

代码

  1 #include <cmath>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <iostream>
  6 #include <algorithm>
  7 
  8 using namespace std;
  9 
 10 #define lim 100000
 11 
 12 int stk[lim];
 13 
 14 class BigNum
 15 {
 16 private:
 17     int s[lim];
 18     
 19     char gc(void)
 20     {
 21         return getchar();
 22     }
 23     
 24     void pc(char c = '\n')
 25     {
 26         putchar(c);
 27     }
 28     
 29     int gl(void)
 30     {
 31         int len = lim;
 32         
 33         while (!s[--len] && len);
 34         
 35         len = len == 0 ? 1 : len; 
 36         
 37         return len;
 38     }
 39     
 40 public:
 41     BigNum(void)
 42     {
 43         memset(s, 0, sizeof(s));
 44     }
 45     
 46     void read(void)
 47     {
 48         int tot = 0, len = 0;
 49         
 50         for (char c = gc(); c >= '0'; c = gc())
 51             stk[++tot] = c - '0';
 52             
 53         while (tot)s[++len] = stk[tot--];
 54     }
 55     
 56     void print(void)
 57     {       
 58         for (int len = gl(); len; )
 59             pc(s[len--] + '0');
 60     }
 61     
 62     void println(void)
 63     {
 64         print(); pc();
 65     }
 66     
 67     int mod4(void)
 68     {
 69         int res = 0;
 70         
 71         for (int len = gl(); len; )
 72             res = (res*10 + s[len--]) & 3;
 73             
 74         return res;
 75     }
 76     
 77     void div4(void)
 78     {
 79         for (int len = gl(); len; --len)
 80             s[len - 1] += (s[len] & 3)*10, s[len] >>= 2;
 81             
 82         s[0] = 0;
 83     }
 84     
 85     bool not0(void)
 86     {
 87         if (gl() > 1 || s[1])
 88             return true;
 89         return false;
 90     }
 91 }num;
 92 
 93 const int MOD = 1e9;
 94 
 95 int f[lim][2];
 96 int g[lim][2];
 97 
 98 void Min(int &a, int b)
 99 {
100     a = min(a, b);
101 }
102 
103 void add(int &a, int b)
104 {
105     a += b;
106     
107     if (a >= MOD)
108         a -= MOD;
109 }
110 
111 signed main(void)
112 {
113     num.read();
114     
115     int tot = 0;
116     
117     while (num.not0())
118         stk[++tot] = num.mod4(), num.div4();
119         
120     reverse(stk + 1, stk + 1 + tot);
121     
122     memset(g, 0, sizeof(g));
123     memset(f, 0x3f3f3f3f, sizeof(f));
124     
125     f[0][0] = 0; g[0][0] = 1;
126     f[0][1] = 1; g[0][1] = 1; 
127     
128     for (int i = 1; i <= tot; ++i)
129     {
130         Min(f[i][0], f[i - 1][0] + stk[i]);
131         Min(f[i][0], f[i - 1][1] + 4 - stk[i]);
132         Min(f[i][1], f[i - 1][0] + stk[i] + 1);
133         Min(f[i][1], f[i - 1][1] + 3 - stk[i]);
134     }
135     
136     for (int i = 1; i <= tot; ++i)
137     {
138         if (f[i][0] == f[i - 1][0] + stk[i])
139             add(g[i][0], g[i - 1][0]);
140         if (f[i][0] == f[i - 1][1] + 4 - stk[i])
141             add(g[i][0], g[i - 1][1]);
142         if (f[i][1] == f[i - 1][0] + stk[i] + 1)
143             add(g[i][1], g[i - 1][0]);
144         if (f[i][1] == f[i - 1][1] + 3 - stk[i])
145             add(g[i][1], g[i - 1][1]);
146     }
147    
148     printf("%d\n", g[tot][0]);
149 }