UVA 10306 e-Coins

可以看成三维的DP, dp[i][X][Y]表示使用前i种icon使得x总和为X且y总和为Y的所有解决方案中icon的最少数量，然后进行递推就行了，注意使用二维滚动数组来模拟三维的DP,x和y的迭代顺序都是从大到小。X和Y取值范围都是0到S

#include <stdio.h>
#define		INF		0x7fffffff

struct coin{
	int x;
	int y;
};
struct coin arr[50];
int dp[350][350];

void func(int m, int s){
	int i, x, y, k;
	int min_icon;

	
	for(x=s; x>=0; x--){
		for(y=s; y>=0; y--){
			if(x==0 && y==0)
				dp[x][y] = 0;
			else
				dp[x][y] = -1;
		}
	}

	for(i=1; i<=m; i++){
		for(x = s; x>=0; x--){
			for(y = s; y>=0; y--){
				if(x*x + y*y > s*s){
					dp[x][y] = -1;
					continue;
				}

				for(k=1; x-k*arr[i].x>=0&&y-k*arr[i].y>=0; k++){
					if(dp[x-k*arr[i].x][y-k*arr[i].y]!=-1 && (dp[x-k*arr[i].x][y-k*arr[i].y]+k<dp[x][y] || dp[x][y]==-1))
						dp[x][y] = dp[x-k*arr[i].x][y-k*arr[i].y]+k;
				}
			}
		}
	}

	min_icon = INF;
	for(x=s; x>=0; x--){
		for(y=s; y>=0; y--){
			if(x*x+y*y==s*s && dp[x][y]!=-1 && dp[x][y]<min_icon)
				min_icon = dp[x][y];
		}
	}

	if(INF == min_icon){
		printf("not possible\n");
	}
	else{
		printf("%d\n", min_icon);
	}
}


int main(void){
	int n, m, i, s;

	//freopen("input.dat", "r", stdin);
	scanf("%d", &n);
	while(n--){
		scanf("%d %d", &m, &s);
		for(i=1; i<=m; i++){
			scanf("%d %d", &(arr[i].x), &(arr[i].y));
		}
		func(m, s);
	}
}