题目大意：现在有一种新型货币，它的价值分为传统价值x和IT价值y，价值计算方式为sqrt(x*x+y*y)，现给一些类型的货币和要达到的目标价值，计算达到目标所需的最少货币数目。注意计算方法是sqrt(所有x和y和的平方和)。
二维完全背包问题？
1 #include <cstdio> 2 #include <climits> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 #define MAXN 310 7 8 int dp[MAXN][MAXN]; 9 int x[50], y[50]; 10 11 int main() 12 { 13 #ifdef LOCAL 14 freopen("in", "r", stdin); 15 #endif 16 int T; 17 scanf("%d", &T); 18 while (T--) 19 { 20 int n, target; 21 scanf("%d%d", &n, &target); 22 for (int i = 0; i < n; i++) 23 scanf("%d%d", &x[i], &y[i]); 24 for (int i = 0; i <= target; i++) 25 for (int j = 0; j <= target; j++) 26 dp[i][j] = INT_MAX; 27 dp[0][0] = 0; 28 for (int i = 0; i <= target; i++) 29 for (int j = 0; j <= target; j++) 30 for (int k = 0; k < n; k++) 31 if (i-x[k] >= 0 && j-y[k]>= 0 && dp[i-x[k]][j-y[k]] != INT_MAX) 32 dp[i][j] = min(dp[i][j], dp[i-x[k]][j-y[k]]+1); 33 int ans = INT_MAX; 34 int t = target * target; 35 for (int i = 0; i <= target; i++) 36 for (int j = 0; j <= target; j++) 37 if (i*i + j*j == t && dp[i][j] != INT_MAX) 38 ans = min(ans, dp[i][j]); 39 if (ans != INT_MAX) printf("%d ", ans); 40 else printf("not possible "); 41 } 42 return 0; 43 }