HJ41~HJ50 华为机试题库

HJ41 称砝码

题目：https://www.nowcoder.com/practice/f9a4c19050fc477e9e27eb75f3bfd49c?tpId=37&tqId=21264&rp=1&ru=/exam/oj/ta&qru=/exam/oj/ta&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D37&difficulty=undefined&judgeStatus=undefined&tags=&title=

一个很经典的题，但是我的状态转移过程写得太丑陋导致调了很久…

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main(){
 4     ios_base::sync_with_stdio(false);
 5     cin.tie(NULL);
 6     int n,sum,cnt;
 7     while(cin>>n){
 8         vector<int>m(n);
 9         vector<int>x(n);
10         for(int i=0;i<n;i++)
11             cin>>m[i];
12         for(int i=0;i<n;i++)
13             cin>>x[i];
14         sum=0;
15         for(int i=0;i<n;i++)
16             sum+=m[i]*x[i];
17         vector<vector<bool>>dp(2,vector<bool>(sum+1,0));
18         dp[0][0]=dp[1][0]=1;cnt=1;
19         for(int i=0;i<n;i++){
20             for(int k=0;k<=sum;k++)
21                 dp[i&1][k]=dp[(i+1)&1][k];
22             for(int j=1;j<=x[i];j++){
23                 for(int k=m[i];k<=sum;k++){
24                     if(k-m[i]*j>=0&&dp[!(i&1)][k-m[i]*j]&&!dp[i&1][k]){
25                         dp[i&1][k]=1;
26                         cnt++;
27                     }
28                 }
29             }
30         }
31         cout<<cnt<<endl;
32     }
33 }

 一维dp：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main(){
 4     ios_base::sync_with_stdio(false);
 5     cin.tie(NULL);
 6     int n,sum,cnt;
 7     while(cin>>n){
 8         vector<int>m(n);
 9         vector<int>x(n);
10         for(int i=0;i<n;i++)
11             cin>>m[i];
12         for(int i=0;i<n;i++)
13             cin>>x[i];
14         sum=0;
15         for(int i=0;i<n;i++)
16             sum+=m[i]*x[i];
17         vector<bool>dp(sum+1,0);
18         dp[0]=1;cnt=1;
19         for(int i=0;i<n;i++){
20             for(int j=sum;j>=0;j--)
21                 if(dp[j]){
22                     for(int k=1;k<=x[i];k++)
23                         if(j+m[i]*k<=sum&&dp[j+m[i]*k]==0){
24                             dp[j+m[i]*k]=1;
25                             cnt++;
26                         }
27                 }
28         }
29         cout<<cnt<<endl;
30     }
31 }