【dp】【进制】P3464 [POI2007] WAG-Quaternary Balance 题解

P3464

显然的，先将原数变为四进制的数。

由于算的是进位/不进位的代价最小值和方案数，容易想到 dp。

这里假定该四进制数是从高位到低位的，顺序显然是由低位到高位。

令 \(f_{i,0/1}\) 表示第 \(i\) 位进 / 不进位的最小代价，\(g_{i,0/1}\) 表示的是最小代价下的方案数。

转移是简单的，对当前位的值分讨一下即可。

时空复杂度线性。

代码：

const int N=1e3+10,mod=1e9;
int n,cnt;
int a[N<<2],b[N],temp[N];
int f[N<<2][2],g[N<<2][2];
string s;

int main(){
	cin>>s;
	int n=s.size();
	s=" "+s;
	int len=n;
	for(int i=1;i<=len;i++)
		b[i]=s[i]-'0';
	while(1){
		for(int i=1;i<=len;i++)
			temp[i]=b[i];
		int now=0,lt=0;
		for(int i=1;i<=len;i++){
			now=now*10+temp[i];
			if(lt||now>=4)
				b[++lt]=now/4;
			now%=4;
		}
		a[++cnt]=now;
		len=lt;
		if(!len)
			break;
	}
	reverse(a+1,a+cnt+1);
	f[cnt][0]=a[cnt],f[cnt][1]=4-a[cnt];
	g[cnt][0]=g[cnt][1]=1;
	for(int i=cnt-1;i;i--){
		if(a[i]==3){
			f[i][0]=a[i]+f[i+1][0];
			g[i][0]=g[i+1][0];
			if(f[i+1][0]+1<=f[i+1][1]){
				f[i][1]=f[i+1][0]+1;
				g[i][1]=g[i+1][0];
			}
			if(f[i+1][0]+1>=f[i+1][1]){
				f[i][1]=f[i+1][1];
				g[i][1]=(g[i][1]+g[i+1][1])%mod;
			}
		}else{
			if(f[i+1][1]+1<=f[i+1][0]){
				f[i][0]=a[i]+f[i+1][1]+1;
				g[i][0]=g[i+1][1];
			}
			if(f[i+1][1]+1>=f[i+1][0]){
				f[i][0]=a[i]+f[i+1][0];
				g[i][0]=(g[i][0]+g[i+1][0])%mod;
			}
			if(f[i+1][0]+4-a[i]<=f[i+1][1]+3-a[i]){
				f[i][1]=f[i+1][0]+4-a[i];
				g[i][1]=g[i+1][0];
			}
			if(f[i+1][0]+4-a[i]>=f[i+1][1]+3-a[i]){
				f[i][1]=f[i+1][1]+3-a[i];
				g[i][1]=(g[i][1]+g[i+1][1])%mod;
			}
		}
	}
	if(f[1][0]<f[1][1]+1)
		cout<<g[1][0]<<endl;
	else if(f[1][0]>f[1][1]+1)
		cout<<g[1][1]<<endl;
	else
		cout<<(g[1][0]+g[1][1])%mod<<endl;
	return 0;
}