题目大意：给定一个数n，要求将n表示成一些四进制数之和/差的形式，要求用的数最少，求方案数
光棍节快乐(巨雾
我们将n分解成4进制，从低位到高位考虑
如果这一位是0，，显然不用考虑这位
如果这一位是1，显然从0开始往上加一个比较优，因为如果从0开始减掉3个还不如将高位-1然后把这一位+1
如果这一位是2，要么从0开始加两个，要么从0开始减掉两个
如果这一位是3，那么一定从0开始往下减一个比较优，因为如果从0开始加上三个还不如将高位+1然后把这一位-1
知道这个我们就可以DP了
令f[i]表示从第i位往前的最小花销及方案数
g[i]表示从第i位往前+1的最小花销及方案数
然后转移就自己搞吧。。。
高精度已废。。。
#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define M 2020#define MOD 1000000000using namespace std;struct Big_Int{int num[1010],cnt;friend istream& operator >> (istream &_,Big_Int &x){static char s[1010];int i;scanf("%s",s+1);x.cnt=strlen(s+1);for(i=1;i<=x.cnt;i++)x.num[i]=s[x.cnt-i+1]-'0';return _;}int operator % (int x){int i,re=0;for(i=cnt;i;i–)((re*=10)+=num[i])%=x;return re;}void operator /= (int x){int i;for(i=cnt;i;i–)num[i-1]+=(num[i]%4)*10,num[i]/=4;num[0]=0;while( cnt>0 && !num[cnt] )–cnt;}}n;int stack[M],top;pair<int,int> f[M],g[M];//f[i]表示从第i位往前的最小花销及方案数//g[i]表示从第i位往前+1的最小花销及方案数void Refresh(pair<int,int>& x,pair<int,int> y,int z=0){if(y.first+z<x.first)x.first=y.first+z,x.second=0;if(y.first+z==x.first)(x.second+=y.second)%=MOD;}int main(){int i;cin>>n;while(n.cnt)stack[++top]=n%4,n/=4;memset(f,0x3f,sizeof f);memset(g,0x3f,sizeof g);f[top+1]=make_pair(0,1);g[top+1]=make_pair(1,1);for(i=top;i;i–){switch(stack[i]){case 0:Refresh(f[i],f[i+1]);Refresh(g[i],f[i+1],1);break;case 1:Refresh(f[i],f[i+1],1);Refresh(g[i],f[i+1],2);Refresh(g[i],g[i+1],2);break;case 2:Refresh(f[i],f[i+1],2);Refresh(f[i],g[i+1],2);Refresh(g[i],g[i+1],1);break;case 3:Refresh(f[i],g[i+1],1);Refresh(g[i],g[i+1]);}}cout<<f[1].second<<endl;return 0;}
松树亭亭玉立的耸立在周围小草小花的中间，
