== 소감 ==
|| 2005-12-29 Accepted 1.703 440 ||

== 코드 ==
{{{~cpp
// 10201 - Adventures in Moving: Part IV
#include <iostream>
using namespace std;

//#include <fstream>
//fstream cin("in.txt");

#define MAX_OIL 200
#define MAX_SIZE 101
#define MAX_NUM 1000000000

typedef struct
{
	int length;
	int price;
}Station;

static int totalLength;				/* 워털루에서 대도시까지의 거리 */
static int numStation;				/* 주유소 수 */
static Station station[MAX_SIZE];	/* 주유소 정보 */
static int d[2][MAX_OIL+1];			/* 다이나믹 테이블 */

inline 
int getDistance(int i) 
{ 
	return station[i].length - station[i-1].length; 
}

void input()
{
	cin >> totalLength;
	cin.get();
	numStation = 0;
	while (cin.peek() != EOF && cin.peek() != '\n')
	{
		numStation++;
		cin >> station[numStation].length >> station[numStation].price;
		cin.get();
	}
	cin.get();
}

void initTable()
{
	station[0].length = 0;
	for (int j = 0; j <= MAX_OIL; j++)
	{
		if (100 - station[1].length < 0 || j < 100 - station[1].length)
			d[1][j] = MAX_NUM;
		else
			d[1][j] = (j - 100 + station[1].length) * station[1].price;
	}
}

void process()
{
	int min, cost;
	int i, j, k;
	initTable();

	if (numStation == 1)
	{
		if (totalLength - station[numStation].length > 100 || station[1].length > 100)
			cout << "Impossible\n";
		else
			cout << d[1][totalLength - station[numStation].length + 100] << endl;
		return;
	}


	for (i = 2; i <= numStation; i++)
	{
		for (j = 0; j <= MAX_OIL; j++)
		{
			min = MAX_NUM;
			for (k = 0; k <= MAX_OIL; k++)
			{
				if (k - getDistance(i) < 0 || d[(i-1)%2][k] >= MAX_NUM || j < k - getDistance(i))
					continue;
				cost = d[(i-1)%2][k] + (j - k + getDistance(i)) * station[i].price;
				if (cost < min)
					min = cost;
			}
			d[i%2][j] = min;
		}
	}

	min = MAX_NUM;
	for (j = 100; j <= MAX_OIL; j++)
	{
		if (d[numStation%2][j] < MAX_NUM && d[numStation%2][j] < min && j - (totalLength - station[numStation].length) >= 100)
			min = d[numStation%2][j];
	}
	if (min >= MAX_NUM)
	{
		cout << "Impossible\n";
		return;
	}
	cout << min << endl;
}

int main()
{
	int numCase;
	cin >> numCase;
	cin.get(), cin.get();
	for (int i = 0; i < numCase; i++)
	{
		input();
		process();
		if (i != numCase - 1)
			cout << endl;
	}
	return 0;
}
}}}
----
[AdventuresInMoving:PartIV] [문보창]