Typical DP Contest

Typical DP Contest

お知らせ



このコンテストについて

このコンテストは動的計画法 (Dynamic Programming, DP) の練習をすることを目的として作られています。

DP とは

たとえば、次の問題を考えてみてください。

N (1 ≤ N ≤ 1000) 匹のリスが一列に並んでいる。左から i 匹目のリスには、整数 a_i が書かれている。この中から何匹かのリスにぶどうをのせ、ぶどうの乗ったリスにかかれた整数が左から昇順に並んでいるようにしたい。最大何匹のリスにぶどうを乗せられるか。


ぶどうの乗ったリスのうち、最も右のリスが i 番目であるときのぶどうの乗ったリスの引数の最大値を dp_i とおくと、漸化式

dp_i = max_{1 ≤ j < i, a_j < a_i} {dp_j} + 1

が成り立つことが分かります。このことを利用して上の問題を C++ 言語で解くと、

int a[1010];
int dp[1010];

int main(void){
	int N,i,j;
	
	cin >> N;
	for(i=0;i<N;i++) cin >> a[i];
	
	for(i=0;i<N;i++){
		dp[i] = 1;
		for(j=0;j<i;j++) if(a[i] > a[j]) dp[i] = max(dp[i], dp[j] + 1);
	}
	
	int ans = 0;
	for(i=0;i<N;i++) ans = max(ans, dp[i]);
	cout << ans << endl;
	
	return 0;
}


となります。 このように、漸化式を用いた手法を DP といいます。

ルール



配点

100 点満点です。
問題 ABCDEFGHIJKLMNOPQRST
配点 23444445555555666778


その他