UVa 10306 - e-Coins
传送门
题意
给出数据组数和s，求能不能凑硬币，使得$x^2 + y^2 = s^2$，求出最小硬币个数。
思路
一开始只想着用dp[i]表示凑成i所需的最少硬币，想了很久没想出来。
还是参考了一帆的解题报告
用dp[i][j]表示凑成$x = i, y = j$所需的最少数量。
状态转移方程$dp[i][j] = min(dp[i - coin[k].td][j - coin[k].it] + 1, dp[i][j])$
代码
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 300 + 10;
const int INF = 0x3f3f3f3f;
struct COIN
{
int td, it;
}coin[50];
int dp[MAXN][MAXN];
int GetValue(int i, int j)
{
return i * i + j * j;
}
int main()
{
//freopen("in.txt", "r", stdin);
int T, i, j, n, s, money, k, ans;
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &n, &s);
for (i = 0; i < n; i++)
scanf("%d%d", &coin[i].td, &coin[i].it);
for (i = 0; i <= s; i++)
for (j = 0; j <= s; j++)
dp[i][j] = INF;
dp[0][0] = 0;
ans = INF;
for (i = 0; i < n; i++)
for (j = 0; j <= s; j++)
for (k = 0; k <= s; k++)
{
if (j - coin[i].td >= 0 && k - coin[i].it >= 0 && GetValue(j, k) <= s * s && dp[j - coin[i].td][k - coin[i].it] != INF)
{
dp[j][k] = min(dp[j][k], dp[j - coin[i].td][k - coin[i].it] + 1);
if (GetValue(j, k) == s * s)
ans = min(ans, dp[j][k]);
}
}
if (ans != INF)
printf("%d\n", ans);
else
printf("not possible\n");
}
return 0;
}