首页 > 代码库 > UVa 10306 - e-Coins
UVa 10306 - e-Coins
题目:有m个钱币,有两种价值(xi,yi),现在要求组成面值sum(x)^2+sum(y)^2=s^2的最少硬币数。
分析:dp,二维安全背包。和以为背包相同,只是容量现在是二维的,按递增序枚举两个容量即可;
求解时,枚举所有x^2+y^2=s^2的x和y,取最小即可。
说明:最近开始练习dp(⊙_⊙)。
#include <iostream> #include <cstdlib> #include <cstdio> using namespace std; int x[42],y[42]; int dp[302][302]; int main() { int n,m,s; while (cin >> n) while (n --) { cin >> m >> s; for (int i = 0 ; i <= s ; ++ i) for (int j = 0 ; j <= s ; ++ j) dp[i][j] = 100000; for (int i = 1 ; i <= m ; ++ i) { cin >> x[i] >> y[i]; dp[x[i]][y[i]] = 1; } for (int i = 1 ; i <= m ; ++ i) for (int j = x[i] ; j <= s ; ++ j) for (int k = y[i] ; k <= s ; ++ k) if (dp[j][k] > dp[j-x[i]][k-y[i]]+1) dp[j][k] = dp[j-x[i]][k-y[i]]+1; int max = 100000; for (int i = 0 ; i <= s ; ++ i) for (int j = 0 ; j <= s ; ++ j) if (i*i+j*j == s*s && max > dp[i][j]) max = dp[i][j]; if (max == 100000) printf("not possible\n"); else printf("%d\n",max); } return 0; }
UVa 10306 - e-Coins
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。