题目
原题链接
问题描述
有一架天平和
n
(
1
≤
n
≤
100
)
n(1\leq n \leq 100)
n(1≤n≤100)个砝码,问通过灵活的使用砝码,这个天平可以称出多少种不同的质量。
分析
步骤一:确定状态
步骤二:确定状态转移方程
步骤三:确定边界情况和初始条件
步骤四:确定计算顺序
步骤一:确定状态
以
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]表示有
i
i
i个砝码时,能否称量出质量
j
j
j,1表示可行,0表示不可行。
步骤二:确定状态转移方程
欲求
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j],已知在有
i
−
1
i-1
i−1个砝码的条件下的所有称量情况,接下来就是求处理第
i
i
i个砝码时的所可以得到的称量情况。
1.若不放该砝码,则
d
p
[
i
]
[
j
]
=
d
p
[
i
−
1
]
[
j
]
dp[i][j]=dp[i-1][j]
dp[i][j]=dp[i−1][j];
2.若放,则又有两种情况,于左或于右:
前提当然是
d
p
[
i
−
1
]
[
j
]
dp[i-1][j]
dp[i−1][j]要存在。
if(dp[i-1][j]){
dp[i][j+m[i]]=1;
if(j-m[i]>0)dp[i][j-m[i]]=1;
}
步骤三:确定边界情况和初始条件
边界条件是无论多少砝码,都可以称量出质量
0
0
0
步骤四:确定计算顺序
自上往下,自左往右。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
#define INF 99999999
int dp[105][N];
int a[N];
int n;
int main(){
cin>>n;
dp[0][0]=1;
for(int i=1;i<=n;i++){
cin>>a[i];
dp[i][0]=1;
}
for(int i=1;i<=n;i++){
for(int j=N-1;j>=0;j--){
if(dp[i-1][j]){
dp[i][j]=1;
dp[i][j+a[i]]=1;
dp[i][abs(j-a[i])]=1;
}
}
}
int ans=0;
for(int i=0;i<N;i++){
if(dp[n][i]){
ans++;
cout<<i<<endl;
}
}
cout<<ans-1;
return 0;
}
/*
3
1 4 6
10
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fir(i, a, b) for (int i = (a); i <= (b); i++)
#define rif(i, a, b) for (int i = (a); i >= (b); i--)
const ll N=1e5+5;
const ll mod=1e9+7;
ll n,m,a[105][N];
int main(){
cin>>n;
fir(j,1,n){
cin>>m;
a[j][m]++;
fir(i,1,N-1){
if(a[j-1][i]){
a[j][i]=1;
a[j][i+m]=1;
a[j][abs(i-m)]=1;
}
}
}
ll cnt=0;
fir(i,1,N-1){
if(a[n][i]){
cnt++;
//cout<<i<<" ";
}
}
cout<<cnt;
}