首页 > 代码库 > HDU 1709 The Balance

HDU 1709 The Balance

2024-07-14 09:09:55   221人阅读

题目大意：
给你一堆砝码的质量和一个天平，利用砝码放在天平上可以称出物品的质量，问在1到所有砝码的质量之和的范围内有哪些整数数据是测不到的，如若没有输出0，

否则输出测不出的质量的个数，并在第二行的时候将其一个个输出

 

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1709

 

这题目我考虑的是用DP来做，因为每个砝码质量不大于100，数量不超过100，所以总和不会超过10000，我就给个稍微大于10000的dp数组即可。

dp[i]=1表示i质量能测出，dp[i]=0表示 i 质量测不出。

用一个m表示每次添入新的数据后能达到的质量的最大值。

对于每加入一个新的数据a[i+1],更新一次dp[]，m也更新为m+=a[i+1]

因为砝码放在左和右都可以，所以对于已能称出的数据来说，新来的砝码（放在左边）看成加上它的数据，（那么右边）看成减去它的数据得到的绝对值即可

dp[j+a[i+1]]=1,dp[abs(j-a[i+1])]=1(j在1到m之间，且dp[j]==1）通过循环找到j，因为防止更新的dp[j]影响循环，我建了b[N]数组来保存每次得到的j的值

当然全部弄完以后要加上dp[a[i+1]]=1;因为它单独称也是成立的

 

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4  5 using namespace std; 6  7 #define MAXN 10005 8 int dp[MAXN],unValue[MAXN],b[105];//unValue来存不能测量出来的质量
 9 10 int abs(int x)11 {12     return x>0?x:-x;13 }14 int main()15 {16     int N,a[101],m,cnt,k;//m作为每次dp后的最大值，cnt在后面表示不能称量出来的点的个数17     while(scanf("%d",&N)!=EOF){18         for(int i=0;i<N;i++)19             scanf("%d",&a[i]);20         memset(dp,0,sizeof(dp));21         dp[a[0]]=1,m=a[0];22         for(int i=1;i<N;i++)23         {24             k=0;//k用来找到每次i循环能找到有多少个j已经能称出来的25             for(int j=1;j<=m;j++)26             {27                 if(dp[j]==1){28                     b[k++]=j;29                 }30             }31             for(int j=0;j<k;j++)32             {33                 dp[a[i]+b[j]]=1;34                 dp[abs(a[i]-b[j])]=1;35             }36             dp[a[i]]=1;//这2句要放在循环最后，不然会影响到前面的值37             m+=a[i];38         }39         cnt=0;40         //寻找那些没能成功称出来的点41         for(int i=1;i<=m;i++)42             if(dp[i]==0) unValue[cnt++]=i;43         if(cnt==0) cout<<0<<endl;44         else{45             cout<<cnt<<endl;46             for(int i=0;i<cnt-1;i++)47                 cout<<unValue[i]<<‘ ‘;48             cout<<unValue[cnt-1]<<endl;49         }50     }51     return 0;52 }

 


联系
我们