小M和天平(简单DP)

2019/05/31 15:15
阅读数 101

题目链接:

https://ac.nowcoder.com/acm/problem/13586

题目大意:

小M想知道某件物品的重量,但是摆在他面前的只有一个天平(没有游标)和一堆石子,石子可以放左边也可以放右边。他现在知道每个石子的重量。问能不能根据上述条件,能不能测出所问的重量。

数据范围:

多组数据,第一行一个数N,表示石子个数。(1<=N<=100) 接下来第二行N个数,表示石子的重量。(1<=Wi<=100) 接下来第三行一个数M,表示询问个数。(1<=M<=1000) 接下来M行每行一个数k(1<=k<=1e9),表示一个询问。

具体思路: 

观察数据范围,发现k的范围只是吓人的。这个题的最大的能称量的范围就是10000.也就是说当k大于10000的时候,一定是输出NO。对于另外的情况,两个for循环暴力就可以了。

AC代码:

 1 #include<bits/stdc++.h>
 2 using namespace  std;
 3 # define ll long long
 4 # define inf 0x3f3f3f3f
 5 const int maxn = 2e4+100;
 6 int dp[100+10][maxn];
 7 int a[maxn];
 8 int main()
 9 {
10     int n;
11     while(~scanf("%d",&n))
12     {
13         for(int i=1;i<=n;i++){
14         scanf("%d",&a[i]);
15         }
16         memset(dp,0,sizeof(dp));
17         dp[0][0]=1;
18         for(int i=1; i<=n; i++)
19         {
20             for(int j=0; j<=1000; j++)
21             {
22                 if(dp[i-1][j])
23                 {
24                     dp[i][j]=1;
25                     dp[i][j+a[i]]=1;
26                     dp[i][abs(j-a[i])]=1;
27                 }
28             }
29         }
30         int m;
31         scanf("%d",&m);
32         while(m--)
33         {
34             int tmp;
35             scanf("%d",&tmp);
36             if(tmp<=10000&&dp[n][tmp])
37                 printf("YES\n");
38             else
39                 printf("NO\n");
40         }
41     }
42     return 0;
43 }

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部