HDU 3680 Naughty fairies BigInteger + Java +DP
注：http://poj.org/problem?id=3278 为此题的缩水版 BFS能过
思路：
Step1:将数转换为二进制
Step2:因为有-1的操作 所以不能直接贪心 通过观察可得 b是a的二进制前缀与b是二进制的前缀+1同样重要 考虑 dp[位数][状态] (状态为前缀 和前缀+1)
Step3:建立初值 dp[i][j]=abs(a-toBase10(b的前i+1位))
Step4:
if(b的二进制表示第i位==0) dp[i][0]=min(dp[i-1][0]+1,dp[i-1][1]+2)
dp[i][1]=min(dp[i-1][0]+2,dp[i-1][1]+2)
else dp[i][0]=min(dp[i-1][0]+2,dp[i-1][1]+2)
dp[i][1]=min(dp[i-1][0]+2,dp[i-1][1]+1)
代码（Java）：
import java.io.*;
import java.math.*;
import java.util.*;
publicclass Main {
publicstatic BigInteger one=BigInteger.valueOf(1);
publicstatic BigInteger two=BigInteger.valueOf(2);
publicstatic String tobase2(BigInteger x){
StringBuffer str=new StringBuffer();
while(!x.equals(BigInteger.ZERO)){
if(x.mod(two).equals(BigInteger.ONE)) str.append('1');
else str.append('0');
x=x.divide(two);
}
returnnew String(str);
}
publicstatic BigInteger Min(BigInteger a,BigInteger b){
if(a.compareTo(b)<0) return a;
elsereturn b;
}
publicstatic BigInteger solve(BigInteger a,BigInteger b){
String sb=tobase2(b);
BigInteger dp[][]=new BigInteger[sb.length()][2];
BigInteger tmp=new BigInteger("0");
for(int i=0;i<sb.length();i++){
tmp=tmp.multiply(two);
if(sb.charAt(sb.length()-1-i)=='1') tmp=tmp.add(BigInteger.ONE);
for(int j=0;j<2;j++) {
dp[i][j]=a.subtract(tmp.add(BigInteger.valueOf(j))).abs();
}
}
for(int i=1;i<sb.length();i++)
{
if(sb.charAt(sb.length()-1-i)=='0'){
dp[i][0]=Min(dp[i][0], Min(dp[i-1][0].add(one), dp[i-1][1].add(two)));
dp[i][1]=Min(dp[i][1], Min(dp[i-1][0].add(two), dp[i-1][1].add(two)));
}else{
dp[i][0]=Min(dp[i][0], Min(dp[i-1][0].add(two), dp[i-1][1].add(two)));
dp[i][1]=Min(dp[i][1], Min(dp[i-1][0].add(two), dp[i-1][1].add(one)));
}
}
return Min(dp[sb.length()-1][0], dp[sb.length()-1][1].add(one));
}
publicstaticvoid main(String[] args) {
Scanner cin=new Scanner(System.in);
while(true){
BigInteger b=cin.nextBigInteger();
BigInteger a=cin.nextBigInteger();
if(a.equals(b) && a.equals(BigInteger.ZERO)) break;
if(a.compareTo(b)>=0){
System.out.println(a.subtract(b));
continue;
}else{
BigInteger ans=solve(a,b);
System.out.println(ans);
}
}
cin.close();
}
}