题目大意:给定一个数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 1000000000 using 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; }