UVA 10306 e-Coins 电子硬币完全背包

题意：一种新的硬币，它的价值的计算方法为sqrt(x*x+y*y)，x和y为所有硬币的对应的价值的和，求出最少需要几个硬币能构成总面值s。

完全背包，dp[i][j]表示达到x为i，y为j时需要的最少硬币个数。

代码：

/* 
*  Author:      illuz  
*  Blog:        http://blog.csdn.net/hcbbt 
*  File:        uva10306.cpp 
*  Create Date: 2013-11-08 14:45:19 
*  Descripton:  dp, bag  
*/  
  
#include   
#include   
  
#define min(x, y) (x) > (y)   (y) : (x)  
  
const int MAXN = 505;  
  
int x[50], y[50], t, n, s;  
int dp[MAXN][MAXN];  
bool used[MAXN][MAXN];  
  
int main() {  
    scanf("%d", &t);  
    while (t--) {  
        // the memset init numbers by bit  
        memset(dp, 2, sizeof(dp));  
        memset(used, 0, sizeof(used));  
  
        scanf("%d%d", &n, &s);  
        for (int i = 0; i < n; i++)  
            scanf("%d%d", &x[i], &y[i]);  
  
        used[0][0] = 1;  
        dp[0][0] = 0;  
        int ans = 0x7ffffff;  
        for (int i = 0; i < n; i++)  
            for (int j = 0; j <= s - x[i]; j++)  
                for (int k = 0; k <= s - y[i]; k++) {  
                    int tx = j + x[i], ty = k + y[i];  
                    if (used[j][k] && dp[tx][ty] >




 dp[j][k] + 1) {  
                        used[tx][ty] = true;  
                        dp[tx][ty] = dp[j][k] + 1;  
                        if (tx * tx + ty * ty == s * s)  
                            ans = min(ans, dp[tx][ty]);  
                    }  
                }  
        if (ans != 0x7ffffff)  
            printf("%d\n", ans);  
        else  
            puts("not possible");  
    }  
    return 0;  
}

UVA 10306 e-Coins 电子硬币 完全背包