大致题意： 要把一个高精度大整数表示为若干(4)的幂的和与差，使得所用(4)的幂数量最少。求方案数。
前言
似乎没什么可说的。。。
大力找规律找半天，最后发现是道(DP)题，求心理阴影面积。。。
马上就要吃饭了，也来不及扯啥了，赶紧水完走人。
动态规划
首先，遇上这种题，肯定先把十进制转化为四进制。
考虑我们定义一个结构体(S)，由(f,g)两个变量组成，分别表示数量和方案数。
定义两个(S)变量(A,B)的加法为：
- 若(A.f=B.f)，则返回(S(A.f,A.g+B.g))。
- 否则，返回(f)较小的那一个。
显然，如果要使某一位满足条件，无非是两种方式：加法或减法。
因此，我们设(F_x)和(G_x)分别表示从高到低(DP)到第(x)位，使高于(x)位的都满足条件，第(x)位满足条件/比目标值大(1)（用于退位）的方案数。
则有转移方程：
[F_x=S(F_{x+1}.f+v_x,F_{x+1}.g)+S(G_{x+1}.f+4-v_x,G_{x+1}.g)
]
[G_x=S(F_{x+1}.f+v_x+1,F_{x+1}.g)+S(G_{x+1}.f+3-v_x,G_{x+1}.g)
]
具体实现详见代码。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define LEN 2000
#define X 1000000000
using namespace std;
int t,v[LEN+5];
struct S
{
int f,g;I S(CI x=0,CI y=0):f(x),g(y){}
I friend S operator + (Con S& A,Con S& B) {return A.f^B.f?(A.f<B.f?A:B):S(A.f,(A.g+B.g)%X);}
}F[LEN+5],G[LEN+5];
struct DecSystem
{
int l,a[LEN+5];
I void read()//读入
{
static string s;cin>>s,l=s.length();for(RI i=1;i<=l;++i) a[i]=s[l-i]&15;
}
I int Mod4()//除以4，返回余数（用于进制转化）
{
RI i,w=0;for(i=l;i;--i) a[i]=10*w+a[i],w=a[i]%4,a[i]/=4;W(l&&!a[l]) --l;return w;
}
}n;
int main()
{
RI i;n.read();W(n.l) v[++t]=n.Mod4();//十进制转四进制
for(F[t+1]=S(0,1),G[t+1]=S(1,1),i=t;i;--i)//动态规划
F[i]=S(F[i+1].f+v[i],F[i+1].g)+S(G[i+1].f+4-v[i],G[i+1].g),//转移F
G[i]=S(F[i+1].f+v[i]+1,F[i+1].g)+S(G[i+1].f+3-v[i],G[i+1].g);//转移G
return printf("%d",F[1].g),0;//输出方案数
}