SRM 594 DIV1 Easy - AstronomicalRecords (復習×○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12804&rd=15706
・惑星がｎ個存在する。
・惑星の相対サイズを測るシステムＡ，Ｂが存在する。
・各システムは太陽からの距離が近い順からランダムな数を選び、そのシステムとの相対距離を計算する。
このとき、存在しうる惑星の数の最小値を求める。
解き方
相対距離の最大値は10^9のため全ての値について全探索はできない。
そこで、要素数は最大５０であることから５０＊５０＝２５００分だけの組み合わせに対して調べればよい。
このとき、掛け算で値を考えると小数になるため計算しにくい。
そのため、最小公倍数の計算の仕方を用いて、A[i],B[j]のペアを選んだときＢの要素には全てA[i]をかけ、Aの要素には全てB[j]をかければよい。
上記の処理後は、LCM（Longest Common Sequence）問題に帰着できる。
dpはＡの要素数とＢの要素数の２次元配列を用いる。
dp[i][j]はi,jに到達するまでの最大値と定義し、状態遷移にて答えを求める。
コード
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 AstronomicalRecords {
public:
int gcd(int x,int y){
return y ? gcd(y,x%y) : x;
}
int minimalPlanets(vector<int> A, vector<int> B) {
int n=A.size(),m=B.size();
int ret=0;
FORE(i,0,n)FORE(j,0,m){
int g=gcd(A[i],B[j]);
vector<long long> a,b;
FORE(k,0,n)a.push_back((long long)A[k]*B[j]/g);
FORE(k,0,m)b.push_back((long long)B[k]*A[i]/g);
int dp[n+1][m+1];
memset(dp,0,sizeof(dp));
FORE(k,0,n)FORE(l,0,m){
if(a[k]==b[l])dp[k+1][l+1]=max(dp[k+1][l+1],dp[k][l]+1);
dp[k+1][l]=max(dp[k+1][l],dp[k][l]);
dp[k][l+1]=max(dp[k][l+1],dp[k][l]);
}
FORE(k,0,n+1)FORE(l,0,m+1)ret=max(ret,dp[k][l]);
}
return n+m-ret;
}
};
#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 AstronomicalRecords {
public:
int gcd(int x,int y){
return y ? gcd(y,x%y) : x;
}
int minimalPlanets(vector<int> A, vector<int> B) {
int n=A.size(),m=B.size();
int ret=0;
FORE(i,0,n)FORE(j,0,m){
int g=gcd(A[i],B[j]);
vector<long long> a,b;
FORE(k,0,n)a.push_back((long long)A[k]*B[j]/g);
FORE(k,0,m)b.push_back((long long)B[k]*A[i]/g);
int dp[n+1][m+1];
memset(dp,0,sizeof(dp));
FORE(k,0,n)FORE(l,0,m){
if(a[k]==b[l])dp[k+1][l+1]=max(dp[k+1][l+1],dp[k][l]+1);
dp[k+1][l]=max(dp[k+1][l],dp[k][l]);
dp[k][l+1]=max(dp[k][l+1],dp[k][l]);
}
FORE(k,0,n+1)FORE(l,0,m+1)ret=max(ret,dp[k][l]);
}
return n+m-ret;
}
};
