问题 D: 天平问题
时间限制: 1 Sec 内存限制: 256 MB
提交 状态
题目描述
小C为了试验小X，便为物竞的小X出了一道物理相关的题：现在给出n个质量的砝码，问小X能称出多少种质量的物品，可是总有好事者想要破坏，于是乎，n达到了500，远远超出了小X能够承受的范围，锲而不舍的他决定寻求你们的帮助。
输入
第一行输入一个的正整数N
以下N行每行一个不超过200的正整数，依次表示每个砝码的质量。
输出
输出总共能称出多少种不同质量的物品。
样例输入 Copy
3
1
3
9
样例输出 Copy
13
提示
注意：天平有两边，两边均可放。100%: n<=500 数据保证砝码的质量之和不超过20000
提交状态
GPLv2 licensed by HUSTOJ 2020
刚刚搜了一下这个题，这个讲解更到位
第一个循环可以得到1 3 9 4 10 12 13
第二个循环可以得到 2 8 11 6 7 5
有一个很重要的想法是
因为是天平，所以可以左边一个1 +3 右边一个9，此时能称出一个5。所以才会有一个循环
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[505];
int dp[2000005];
int main()
{//std::ios::sync_with_stdio(false);//std::cin.tie(0);int n;cin>>n;for(int i=1;i<=n;i++){scanf("%d",a+i);}ll ans=0;dp[0]=1;for(int i=1;i<=n;i++){for(int j=20010;j>=a[i];j--)dp[j]=max(dp[j],dp[j-a[i]]);}for(int i=1;i<=n;i++){for(int j=0;j<=20010;j++){dp[j]=max(dp[j],dp[j+a[i]]);}}for(int i=1;i<=20010;i++)if(dp[i]) ans++;cout<<ans;return 0;
}
这个用01背包写的思路是错误的，虽然包含了一种选与不选的思想，但是1+9和3+9都是属于3个里面选2个，所以此方法错误。
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[505];
int dp[505][505];
map<int,int>mp;
int main()
{//std::ios::sync_with_stdio(false);//std::cin.tie(0);int n;cin>>n;for(int i=1;i<=n;i++){scanf("%d",a+i);}ll ans=0;for(int i=1;i<=n;i++)//个背包{for(int j=1;j<=n;j++)//i个物品选j个{dp[i][j]=dp[i-1][j];//不选if(mp[dp[i][j]]==0&&dp[i][j]!=0) {mp[dp[i][j]]=1;ans++;printf("%d\n",dp[i][j]);}dp[i][j]=dp[i-1][j-1]+a[j];if(mp[dp[i][j]]==0&&dp[i][j]!=0) {mp[dp[i][j]]=1;ans++; printf("%d\n",dp[i][j]);}}}cout<<ans;return 0;
}