题目类型 DP
题目意思
有一个天平 天平上最多有20个钩子 现在给出每个钩子与中心点的距离 (距离为负表示在中心点左边 距离为正表示在中心点右边)
如果在距离为 5 的钩子上面挂一个重量为 10 的砝码则 当前的平衡值为 50 这时如果在距离为 -10 的钩子上挂一个重量为 5 的砝码则总的
平衡值为 5×10 + (-10)*5 = 0 则表示天平是平衡的
现在给出每个钩子的位置d(-15 <= d <= 15) 与最多20个砝码的重量wi(1 <= wi <= 25) 问使天平平衡的不同放置方法有多少种
解题方法
由于题目的值的数据范围较小 极值是 -15*25*20 -> 15*25*20 那么可以设计一个这样的状态
dp[i][j] -> 前i个物品 放置出平衡值为 j 的方法数
对于物品 A[p] 放在 钩子 B[q] 上 dp[i][j] += dp[i-1][j-A[p]*B[q]];
最终的答案是 dp[物品数][0] 详细见代码
由于下标可能是负数所以可以用 平移的方法使所有下标均为正的 即 所有下标向右平移 15×25×20
参考代码 - 有疑问的地方在下方留言 看到会尽快回复的
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 100;
int A[maxn], B[maxn];
int dp[21][8000*2];
int main() {
freopen("in", "r", stdin);
//printf("%d\n", 15*25*20);
int P = 15*25*20; // 平移量
int n, m;
while(scanf("%d%d", &n, &m) != EOF) {
for( int i=0; i<n; i++ ) scanf("%d", &A[i]);
for( int i=0; i<m; i++ ) scanf("%d", &B[i]);
memset(dp, 0, sizeof(dp));
for( int i=0; i<m; i++ ) { //枚举第 i 个物品放置在 第 j 个钩子处
for( int j=0; j<n; j++ ) {
if(i == 0) {
dp[0][P+B[i]*A[j]]++; // 第0个物品自己加 注意要加上平移量
continue;
}
for( int k=P*2; k>=B[i]*A[j]; k-- ) {
dp[i][k] += dp[i-1][k-B[i]*A[j]]; // 更新
}
}
}
printf("%d\n", dp[m-1][P]); // dp[m-1][P]为答案 即没平移时的 dp[m-1][0] 平衡值为0表示天平是平衡的
}
return 0;
}