問題
http://community.topcoder.com/stat?c=problem_statement&pm=6186&rd=9823
ある整数から、ある整数へ変換したい。
ある整数からの変換は、１とその数以外の、その整数で割りきれる数を足すことができる。
このとき、最小の変換回数を求める。
解き方
ぱっと見てdpで解く問題。
ただし、整数Ｎ割り切れる数を探すのにＮ/2まで探索しては間に合わない。
そこで、sqrt(Ｎ）まで探索してその数iとN/iの両方で検査する。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class DivisorInc {
public: int countOperations(int N, int M) {
int dp[M+1];
FORE(i,N,M+1)dp[i]=1e+9;
dp[N]=0;
FORE(i,N,M+1){
if(dp[i]==1e+9)continue;
for(int j=2;j*j<=i;j++){
if(i%j!=0)continue;
if(i+j<=M)dp[i+j]=min(dp[i+j],dp[i]+1);
if(i+i/j<=M)dp[i+i/j]=min(dp[i+i/j],dp[i]+1);
}
}
return dp[M]==1e+9 ? -1 : dp[M];
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class DivisorInc {
public: int countOperations(int N, int M) {
int dp[M+1];
FORE(i,N,M+1)dp[i]=1e+9;
dp[N]=0;
FORE(i,N,M+1){
if(dp[i]==1e+9)continue;
for(int j=2;j*j<=i;j++){
if(i%j!=0)continue;
if(i+j<=M)dp[i+j]=min(dp[i+j],dp[i]+1);
if(i+i/j<=M)dp[i+i/j]=min(dp[i+i/j],dp[i]+1);
}
}
return dp[M]==1e+9 ? -1 : dp[M];
}
};