白俊2579号階段を上る

2272 ワード
階段を登る 白駿 DP c言語 さいきかんすう 復帰する テキストリンク
https://www.acmicpc.net/problem/2579
最初に想定したアルゴリズムとコード
踏み始めたばかりの階段は複雑すぎる.
踏まない階段を思い出した.
踏まない階段は1段か2段あります.
n必ずしもn段目の階段を踏む必要はないと仮定する
n個の階段を踏まない最小点数の和はn−2次とn−3次の小数とn次の点数の和であると考えられる.
#include <stdio.h>

int main()
{
	int minus[303];//밟지 않는 계단의 점수 합을 이 배열에 저장할 것
	int i, n, total;
	scanf("%d", &n);
	total = 0;
	for (i = 0; i < 3; i++)
	{
		minus[i] = 0; //if문을 쓰지 않고 일반화하기 위해 일단 처음 세개는 값을 0으로 주었다.
	}
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &minus[i + 2]);
		total += minus[i + 2];//여가서 total은 모든 계단의 점수 합
		minus[i + 2] += minus[i] < minus[i - 1] ? minus[i] : minus[i - 1];
	}
	total -= minus[n] < minus[n + 1] ? minus[n] : minus[n + 1];//minus는 minus[n+2]까지 저장되나 n+2번째 칸은 밟아야하므로 생각할 필요X, 마지막칸 전과 전전 중 하나는 밟지 말아야 하므로(둘다 밟으면 마지막 칸을 밟을수 없다.) 둘 중 하나를 비교하여 더 작은 것이 최소한의 점수로 계단을 밟지 않는 것이다. 
	printf("%d", total);
}
2番目のアルゴリズム
これは階段を踏む点数の最大値を直接求める方法です.
n番目のステップについては、n-1番目またはn-2番目のステップを歩くので、2つのスコアの和の最大値の1つを選択し、n番目のステップのスコアに加算すればよい.
実際には、それは当然ではありません.もしあなたがn-1段の階段を踏んだら、n-2段の階段を踏んだとき、それを排除しなければなりません.
すなわち、n−3次およびn−1次までの数字の和またはn−2次までの和では、より大きなものを選択すべきである.
#include <stdio.h>

int main()
{
	int stair[303];
	int total[303];
	int i, N;
	scanf("%d", &N);
	for (i = 0; i < 3; i++)
	{
		total[i] = 0;
		stair[i] = 0;// 1,2,3번째 계단에서 문제가 없도록 0으로 설정
        이러면 첫번째 계단의 경우 무조건 0이 더해지므로 자기 자신
        두번째 계단의 경우 0이 더해지거나 1번째 계단과의 합이므로 1번째 계단과의 합
        세번째 계단의 경우 첫번째 계단과의 합 또는 0번째까지의 합과 두번째 계단의 합 즉, 두번째 계단과의 합이므로 둘중 더 큰 걸 고르게 된다.
	}
	for (i = 3; i < N + 3; i++)
	{
		scanf("%d", &stair[i]);
		total[i] = stair[i];
	}
	for (i = 0; i < N; i++)
	{
		total[i + 3] += total[i + 1] > total[i] + stair[i + 2] ? total[i + 1] : total[i] + stair[i + 2];
	}
	printf("%d", total[N + 2]);
	return 0;
}
DialogFragmentは行かない
Java)CodeUp 100第[61-80]