题目描述
你有一架天平和 N 个砝码,这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WN。
请你计算一共可以称出多少种不同的正整数重量?
注意砝码可以放在天平两边。
算法1
(dp) O(nm)
由实际含义可以,f[i][j]=f[i][-j] 因为可以通过镜像的操作而得到,故而f[i][j-w]=f[i][w-j]=f[i][abs(j-w)]。就避免了数组下标为负数的情况
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 110, M = 2e5 + 10;
int sum;
int n;
int w[N];
bool f[N][M];
int main() {
cin>>n;
for (int i = 1; i <= n; i++)
{
scanf("%d", &w[i]);
sum+=w[i];
}
f[0][0]=true;
for (int i = 1; i <= n;i++)
for (int j = 0; j <=sum;j++)
f[i][j]=f[i-1][j]||f[i-1][j+w[i]]||f[i-1][abs(j-w[i])];
//只要有一个非空,f[i][j]就非空
int ans = 0;
for (int i = 1; i <=sum;i++)
if(f[n][i])ans++;//不为零说明可以选出这个质量的砝码
cout << ans;
return 0;
}
算法2
(暴力枚举 过一半的数据)
C++ 代码
#include<stdio.h>
int n;
int res;
int w[1000000];
bool st[100000];
void dfs(int k,int sum)//表示k个的砝码,重量是sum
{
if(k>n)//k>n 说明选完n个砝码
{
if(sum>0&&!st[sum])// 判断选出来的n个砝码的重量是否没被标记过 ,如没标记则答案加1
{
res++;
st[sum]=true;//标记这个重量
return;
}
}
//还没选够n个砝码
else
{
dfs(k+1,sum-w[k]);//砝码放右边
dfs(k+1,sum);//跳过,不选用当前的砝码
dfs(k+1,sum+w[k]);//砝码放左边
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
dfs(0,0);
printf("%d",res);
}
汤神,我高数跟定你啦
真是清清又爽爽啊
求大佬解释一下为什么这里的数组还需要开两倍啊?
我也想知道这里为什么只有开两倍才能过, 这里abs不是没有偏移量嘛
我觉得如果数据只有一个砝码,重量是1e5,那么当j=1e5,转移时的f[i][j+w[i]]就越界了,所以开了两倍。
清晰了!!!
原来如此,感谢大佬
可以不开两倍
#include <bits/stdc++.h> using namespace std; const int N = 110, M = 1e5 + 10; int sum; int n; int w[N]; bool f[N][M]; int main() { cin>>n; for (int i = 1; i <= n; i++) { scanf("%d", &w[i]); sum+=w[i]; } f[0][0]=true; for (int i = 1; i <= n;i++) for (int j = 0; j <=sum;j++) { f[i][j]=f[i-1][j]||f[i-1][abs(j-w[i])]; if (j + w[i] <= sum) f[i][j] |= f[i - 1][j + w[i]]; } //只要有一个非空,f[i][j]就非空 int ans = 0; for (int i = 1; i <=sum;i++) if(f[n][i])ans++;//不为零说明可以选出这个质量的砝码 cout << ans; return 0; }
只要判断一下数组别越界就行
可是说的是总重
%%%
orz
数据范围不是说总重量不超过1e5吗?怎么申请空间为2e5才正确
应该是不超过1e6,第六组数据总和就是1e6。hhhh
题目说N个砝码总重不超过1e5是不是题目有问题
应该是滴
应该是y总加强数据了,官网1e5能过
####bfs过四个
####为什么dfs可以过五个!!!
import java.io.*; import java.util.*; public class Main{ public static void main(String[] args) throws Exception { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(in.readLine().trim()); String[] s0 = in.readLine().split("\\s+"); int[] h = new int[110]; for(int i = 0;i<n;i++) { h[i] = Integer.parseInt(s0[i]); } boolean[] use = new boolean[100010]; long res = 0; Queue<int[]> q = new LinkedList<>(); q.add(new int[]{0,0}); // 次数 + 重量 while(!q.isEmpty()) { int[] a = q.poll(); if(a[0]>n) { if(a[1]>0 && !use[a[1]]) { res++; use[a[1]] = true; } } else { q.add(new int[]{a[0]+1,a[1]-h[a[0]]}); q.add(new int[]{a[0]+1,a[1]}); q.add(new int[]{a[0]+1,a[1]+h[a[0]]}); } } out.println(res); out.flush(); } }
汤老师,你是我的神!
太妙了这个dp负数的处理!
orz不知道怎么理解这个绝对值
如果你j等于负数,那把当前j所有左右两边砝码交换位置,j就是正数了,也就是说如果j等于负数的情况成立,那正数也一定能凑出来,比如左边放5右边2,等于-3,反过来左边2右边5就是3了
tql,这个解释太清晰了
意思是正负是成对出现的嘛,负数的状态可以用正数的状态代替?这样理解对不对啊
对 正数可以本身就是凑出来的 也可以是负数➕绝对值出来的也结果 重复标记没有影响
汤老师算法讲得好!
orz
汤老师,英一事变后我打算跟你学英语
妙的布得鸟啊,汤老师
豪!
f[i-1][j] || (f[i-1][j+w]&&f[i-1][w]) 这样总重量即为j方程对不对
为什么我也是这样写的,外层for枚举砝码,内层for枚举重量(sum),然后超时了....
用bitset才过
好吧,我看错题了,我还以为每个砝码都1e5…
佬,太厉害了
我有一个问题,为什么dfs中sum大于0才是答案呢?如果我两边都是1,那么称重不就是0吗?我发现我写的暴搜,少了你这一步,就会多加一个1,当n>=4的时候
第一个图状态表示有问题呀,选和不选状态表示反了
sum可以换成sum[i]来表示w[i]的前缀和,这样遍历j的时候,只需要循环sum[i]次就可以了,因为超过前i个砝码的总重量的j是达不到的
厉害得布达鸟啊