UVA10306

 1 /*题意
 2 共有 T 组测试
 3 输入N ,S,表示有n种物品,
 4 接下来N行
 5 输入x,y  。每种物品有x, y两个价值,并且可以有无限多个。
 6 使得(x1+x2+....)^2 + (y1+y2+....)^2 = s ^ 2。
 7 输出最少要多少个物品,如果不可能则输出not possible
 8 例如:
 9 1
10 3 5
11 3 0
12 0 4
13 5 5
14 答案是2,(3 0 )和(4 0) 这2种。(3+0)^2+(4+0)^2=5^2
15
16 解答:
17 设  j = x1+ x2+... , k= y1+y2+...
18 dp[j][k] 表示当前状态需要多少个 。
19 辣么 dp[j][k]=min(dp[j][k],dp[j-Wi][k-W2i]+1);
20
21
22 // 感谢学长们的帮助,愿我能做的越来越好~
23 */
24
25 #include<cstdio>
26 #include<cstring>
27 #include<algorithm>
28 #define INF 1000005
29 using namespace std;
30 int w[50],w2[50];
31 int dp[305][305];
32 int main()
33 {
34     int t,n,s;
35     scanf("%d",&t);
36     while(t--)
37     {
38         scanf("%d%d",&n,&s);
39         for(int i=0;i<n;i++)
40             scanf("%d%d",&w[i],&w2[i]);
41         for(int i=0;i<=s;i++)
42             for(int j=0;j<=s;j++)
43                 dp[i][j]=INF;
44         dp[0][0]=0;
45         for(int i=0;i<n;i++)
46         {
47             for(int j=w[i];j<=s;j++)
48             {
49                 for(int k=w2[i];k<=s;k++)
50                 {
51                     if(dp[j-w[i]][k-w2[i]]!=INF)
52                     dp[j][k]=min(dp[j][k],dp[j-w[i]][k-w2[i]]+1);
53                 }
54             }
55         }
56         int ans=INF;
57         for(int i=0;i<=s;i++)
58             for(int j=0;j<=s;j++)  // 每个状态都找一遍,找到满足条件且用的最少的
59                 if( (i*i+j*j==s*s) && dp[i][j]!=INF )
60                     ans=(dp[i][j]<ans) ? dp[i][j]:ans;
61         if(ans!=INF) printf("%d\n",ans);
62         else printf("not possible\n");
63     }
64     return 0;
65 }
66 //希望自己能再找出另一种写法> <
时间: 10-13

UVA10306的相关文章