题目
源地址:
http://poj.org/problem?id=2818
理解
感觉很水的一道题,不知道为什么交题的人很少(吐槽一下坑爹的美元换算)。用DFS水掉了,分别从dispenser到pennies来算一遍就OK。我本以为用四个for也能过,但是discuss上面有人说过不了,TLE。有时间我试试看。
代码
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
using namespace std;
const int INF = 10000;
int num[4], tmp[4], result[4];
int total, money;
bool success;
void DFS(int dep, int remained)
{
if (dep == 4)
{
if (remained == 0)
{
int sum = tmp[0] + tmp[1] + tmp[2] + tmp[3];
if (sum < total)
{
for (int i = 0; i < 4; i++)
result[i] = tmp[i];
total = sum;
}
success = true;
}
return;
}
for (int j = 0; j <= num[dep]; j++)
{
tmp[dep] = j;
if (dep == 0)
DFS(dep + 1, remained - 25 * j);
else if (dep == 1)
DFS(dep + 1, remained - 10 * j);
else if (dep == 2)
DFS(dep + 1, remained - 5 * j);
else if (dep == 3)
DFS(dep + 1, remained - j);
}
}
int main(int argc, char const *argv[])
{
while (scanf("%d%d%d%d%d", &num[0], &num[1], &num[2], &num[3], &money) && (num[0] || num[1] || num[2] || num[3] || money))
{
total = INF;
success = false;
DFS(0, money);
if (success)
printf("Dispense %d quarters, %d dimes, %d nickels, and %d pennies.\n", result[0], result[1], result[2], result[3]);
else
printf("Cannot dispense the desired amount.\n");
}
return 0;
}
更新日志
- 2014年07月15日 已AC。