【蓝桥杯】砝码称重

以你之姓@ 2024-03-30 10:14 22阅读 0赞

[3417. 砝码称重 - AcWing题库][3417. _ - AcWing]

题意：

![29f26757e1174102b819a74e4f568b98.png][]思路回顾：

首先这道题一开始我没想用DP做，看到标签是入门题就没想DP qwq

其实这就是一个普通背包

一开始设计状态设计不出来，刚开始设的是dp\[i\]\[j\]表示前i个物品能表示j种重量

显然是不行的，**答案不能写在参数里**

而且这样状态转移也会很麻烦，少了a\[i\]，上一层的状态也表示不了，因此这样设计一定是错的

后来看到小数据是15，那就暴力dfs吧

然后在写dfs的时候设计的状态设对了，(i,j)表示前i个物品表示重量为j的方案数

然后去枚举决策，因为它是一个天平，有三种决策：

放左边，放右边，不放

这样设计状态后，状态转移就容易多了

**因此我们设计完状态之后，发现不好转移，大概率是状态设计错了qwq**

放左就是从(i-1,j+a\[i\])转移过来

放右就是从(i-1,abs(j-a\[i\]))转移过来

不放就是从(i-1,j)转移过来

然后i>n是出口，我们用set维护重量种类数即可

这样的复杂度是3^n，显然跑不了所有，但是可以骗分

**对于OI赛制的题，要按照小数据范围的提示进行一些暴力骗分qwq**

那么暴力我们写出来了，再去试了DP，这次状态设计为：dp\[i\]\[j\]表示前i个物品重量为j

然后状态转移方程也成功写出来了，但是我却错在答案统计上....

显然答案是从dp\[n\]\[j\]转移过来的，枚举一下，放set里面维护种类数就好了

但是我却枚举了所有的状态然后统计

**所以dp数组推出来了之后的答案统计也要搞清楚**

**好像该去学一下记忆化搜索咋写，这样只会爆搜不会DP的时候就直接写个记忆化就好了**

**Code：**

暴力:

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=20;
    set<int> S;
    int n;
    int a[mxn];
    void dfs(int i,int j){
    	if(i>n){
    		if(j!=0) S.insert(j);
    		return;
    	}
    	dfs(i+1,j);
    	dfs(i+1,j+a[i+1]);
    	dfs(i+1,abs(j-a[i+1]));
    }
    int main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	dfs(0,0);//爆搜
    	cout<<S.size()<<'\n';
    }

DP:

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e2+10,mxv=2e5+10;
    set<int> S;
    int n,sum=0;
    int a[mxn],dp[mxn][mxv];
    int main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	memset(dp,0,sizeof(dp));
    	cin>>n;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	dp[0][0]=1;
    	for(int i=1;i<=n;i++){
    		for(int j=0;j<=1e5;j++){
    			dp[i][j]=(dp[i-1][j]+dp[i-1][j+a[i]])+(dp[i-1][abs(j-a[i])]);
    		}
    	}
    	for(int i=1;i<=1e5;i++){
    		if(dp[n][i]) S.insert(i);
    	}
    	cout<<S.size()<<'\n';
    }

**总结：**

**DP：**

**状态设计的时候，答案不能放在参数里，它本身就是答案**

**状态转移的时候如果发现很难转移，基本就是状态设计错了**

**然后dp数组推出来了之后的答案统计也要搞清楚**

**其他：**

**对于OI赛制的题，要按照小数据范围的提示进行一些暴力骗分**

[3417. _ - AcWing]: https://www.acwing.com/problem/content/3420/
[29f26757e1174102b819a74e4f568b98.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c5708ace7f66493892fee36202e9d79d.png