kmjp's blog

競技プログラミング参加記です

yukicoder : No.979 Longest Divisor Sequence

これは★3の割には簡単より。
https://yukicoder.me/problems/no/979

問題

正整数列Aが与えられる。
Aの部分列のうち、真に単調増加で、かつ先頭以降の要素は直前の要素の倍数になっているものの最長長を求めよ。

解法

dp(i,k) := 先頭i要素目までの部分列のうち、末尾の要素がkであるようなものの最長長
とする。
dp(i,k)の状態に対し、A[i+1]を追加するかどうかを考えると、

  • k!=A[i+1]の場合 dp(i+1,k)=dp(i,k)
  • k=A[i+1]の場合 \displaystyle dp(i+1,k)=max(1,dp(i,k),max_{d|k, d \lt k}(dp(i,d)+1))

よってDPテーブルのほとんどは変化しない。
そこでDPテーブルをできるだけ使いまわすように上記式の通りに遷移させればよい。

int N;
int P[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int ret=0;
	FOR(i,N) {
		cin>>x;
		int ma=1;
		for(j=1;j*j<=x;j++) if(x%j==0) {
			if(x!=1) ma=max(ma,P[j]+1);
			if(j>1) ma=max(ma,P[x/j]+1);
		}
		P[x]=max(P[x],ma);
		ret=max(ret,ma);
	}
	cout<<ret<<endl;
}

まとめ

やることは割とストレートだしね。