imported>Unknown at 05:22, 7 February 2021

2021-02-07T05:22:26Z

New page

== 소감 ==
{| class="wikitable"
|-
| 2005-12-29 Accepted 1.703 440
|}

== 코드 ==
// 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]] [[문보창]]

AdventuresInMoving:PartIV/문보창 - Revision history

imported>Unknown at 05:22, 7 February 2021