思路:动态规划。首先定义平衡度
b
a
l
a
n
c
e
=
Σ
w
[
i
]
∗
c
[
k
]
balance=Σw[i]*c[k]
balance=Σw[i]∗c[k],w是砝码重量,c是砝码位置,显然当balance=0时,杠杆是平衡的。balance>0右端低,balance<0左端低。
定义:
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j]表示使用前i个砝码时,平衡度达到j时杠杆平衡的方案数。
#include<iostream>
using namespace std;
const int maxn=27;
int dp[maxn][15001];
int w[maxn];
int c[maxn];
int main(){
int n_c,n_w;
cin>>n_c>>n_w;
int i;
for(i=1;i<=n_c;i++)cin>>c[i];
for(i=1;i<=n_w;i++)cin>>w[i];
dp[0][7500]=1;
int j,k;
for(i=1;i<=n_w;i++){
for(j=0;j<=15000;j++){
for(k=1;k<=n_c;k++){
if(j+w[i]*c[k]>=0)dp[i][j+w[i]*c[k]]+=dp[i-1][j];
}
}
}
cout<<dp[n_w][7500]<<endl;
return 0;
}