Submission #811775


Source Code Expand

Copy
/*
atcoder 柱柱柱柱柱
柱の高さがN個与えられる。柱から右に1つまたは2つ移動できるが、移動するたび柱の高さの差の絶対値だけコストがかかる。
N番目の柱に移動するときにかかる最小のコストを求める.
*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/*現在地からの移動コストを求める*/
long long getCost(const int* poleheight, int curposition, int nmove){
	
	return abs(poleheight[curposition]-poleheight[curposition+nmove]);
}

/*動的計画法が使えるのでk番目の柱に到達するのに必要なコストを逐次的に計算して求める.*/
int main()
{
	int *poleheight;	//柱の高さ
	long long *polecost;	//柱到達にかかるコスト
	int npole;			//柱の数
	int i;
	long long ncost1, ncost2;	//1進む、2進むのに必要なコスト
	//柱の数を入力から受け取り、必要な配列(コストと高さ)を確保する
	scanf("%d", &npole);
	poleheight = (int*)malloc(sizeof(int)*npole);
	polecost = (long long*)malloc(sizeof(long long)*npole);
	//柱の高さを標準入力から受け取る
	for(i=0;i<npole;i++)scanf("%d", &poleheight[i]);
	//初期条件として0番目と1番目の最小コストは確定
	polecost[0] = 0;
	polecost[1] = getCost(poleheight, 0, 1);
	//探索していきi番目の柱到達までの最小コストを求めていく
	for(i=0;i<npole-2;i++){
		//現在地からの移動コストを取得
		ncost1 = getCost(poleheight, i, 1);
		ncost2 = getCost(poleheight, i, 2);
		//この時点でi番目以前の値は確定、i+2番目以降は未決定
		//i+1番目は一つ前からの合計移動コストと今入っている値を比較して小さい方に確定
		if(polecost[i+1]>(ncost1+polecost[i]))polecost[i+1]=ncost1+polecost[i];
		polecost[i+2]=ncost2;
	}
	printf("%lld\n", polecost[npole-1]);
	free(polecost);
	free(poleheight);
}




Submission Info

Submission Time
Task C - 柱柱柱柱柱
User sqrt36
Language C (GCC 5.4.1)
Score 0
Code Size 1962 Byte
Status
Exec Time 22 ms
Memory 1280 KB

Compile Error

./Main.c: In function ‘main’:
./Main.c:24:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &npole);
  ^
./Main.c:28:22: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  for(i=0;i<npole;i++)scanf("%d", &poleheight[i]);
                      ^

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 0 / 100 sample_01.txt, sample_02.txt, sample_03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt
Case Name Status Exec Time Memory
sample_01.txt 2 ms 128 KB
sample_02.txt 2 ms 128 KB
sample_03.txt 2 ms 128 KB
subtask1_01.txt 2 ms 128 KB
subtask1_02.txt 2 ms 128 KB
subtask1_03.txt 2 ms 128 KB
subtask1_04.txt 22 ms 1280 KB
subtask1_05.txt 22 ms 1280 KB
subtask1_06.txt 22 ms 1280 KB
subtask1_07.txt 22 ms 1280 KB