1111: [POI2007]四进制的天平Wag
题意：
用一些四进制数，相减得到给定的数，四进制数的数量应该尽量少，满足最少的条件下，求方案数。
分析：
这道题拖了好久啊。
参考Claris的博客。
首先将四进制数转化为四进制数。
一种的可行构造方案是四进制数上每一位的和。例如：$(003)_4$可以有3个$4^0$的砝码组成，当然也可以向前一位借位，$(010)_4-(001)_4$，此时就需要2个砝码了。
所以可以推出：每位最多借一位，最高位最高是n+1位。所以可以dp表示当前是否借位过。
f[i]表示到第i位，不向i+1借位的数字最少的个数，以及方案数。g[i]表示向i+1借位。即i+1位的一个数变成4个i位的数字，然后做差。（此处不管是否向高位借位，都不记录高位的贡献）
$f[i] = merge(f[i - 1] + b[i] ,g[i - 1] + b[i] + 1)$
$g[i] = merge(f[i - 1] + 4 - b[i], g[i - 1] + 3 - b[i])$
第一个转移方程表示当前这一位不向高位借位：
1、如果低位也不向它借位，低位自己的答案是f[i-1]，那么只需要b[i]个$4^i$的砝码即可组成这一位的答案。
2、如果低位向它借位，低位的答案g[i-1]，本来b[i]个即可满足，现在需要再增加一个给低位。例如：样例$(2212)_4$到第二位时，如果第一位向它借位，那么第一位的砝码是4-1-1=2，这一位的砝码是4，所以共3个。
第二个转移方程表示当前这一位不向高位借位：
1、如果低位不向它借位，同样加上f[i-1]，而它需要4-b[i]个重为$4^i$的砝码。
2、如果低位向它借位，同样加上g[i-1]，它需要3-b[i]个重为$4^i$的砝码，其中一个给了下一位了，那么此时是否还满足呢？样例$(2212)_4$到第二位时，借位后是16-4-4-4=4，下一位也要借位是4-1-1=2，中间其实可以消掉一个，二式相加得到16-4-4-1-1=6，刚好满足前两位的和是6
代码：
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
#include<bitset>
using namespace std;
typedef long long LL; inline int read() {
int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;
for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;
} const int N = ;
char s[N];
int a[N], b[N];
struct Node{
int x, y;
Node() {}
Node(int _x,int _y) { x = _x, y = _y; }
Node operator + (int a) { return Node(x + a, y); }
Node operator + (Node A) {
if (x == A.x) return Node(x, (y + A.y) % );
return x < A.x ? *this : A;
}
}f[N], g[N]; int main() {
scanf("%s", s + );
int len = strlen(s + ), n = ;
for (int i = ; i <= len; ++i) a[i] = s[len - i + ] - ''; while (len) { // 分解为四进制数，每次找到模4剩下的余数
a[] = ;
for (int i = len; i; --i)
a[i - ] += (a[i] & ) * , a[i] >>= ; // 第i位模4后的余数，到下一位乘10
b[++n] = a[] / ;
for (; len && !a[len]; len --);
} n ++;
f[] = Node(, ); g[] = Node(1e9, );
for (int i = ; i <= n; ++i) { // 从低位往高位dp
f[i] = (f[i - ] + b[i]) + (g[i - ] + (b[i] + ));
g[i] = (f[i - ] + ( - b[i])) + (g[i - ] + ( - b[i]));
}
cout << f[n].y;
return ;
}