首页 > 代码库 > POJ 1837 Balance

POJ 1837 Balance

2024-07-16 04:26:10   214人阅读

1.poj 1837 Balance :http://poj.org/problem?id=1837

这道题个人认为不好想，要不是CJ的耐心指导，我可能会困很久吧orz。。写一篇解题报告来纪念一下~~噶呜！

先来说说题意：

   这道题用到了一个物理知识：力臂=重量 *臂长 = w[i]*c[k]。

   有一个天平，天平左右两边各有若干个钩子，总共有C个钩子，有G个钩码，求将钩码全部挂到钩子上使天平平衡的方法的总数。

   其中可以把天枰看做一个以x轴0点作为平衡点的横轴，当平衡度k=0时，说明天枰达到平衡，k>0，说明天枰倾向右边（x轴右半轴），k<0则左倾，因此可以定义一个 状态数组dp[i][k]，意为在挂满前i个钩码时，平衡度为k的挂法的数量。由于距离c[i]的范围是-15~15，钩码重量的范围是1~25，钩码数量最大是20.因此最极端的平衡度是所有物体都挂在最远端，因此平衡度最大值为j=15*20*25=7500。原则上就应该有dp[ 1~20 ][-7500 ~ 7500 ]。因此为了不让下标出现负数，做一个处理，使使得数组开为 dp[1~20][0~15000]，则当j=7500时天枰为平衡状态。

   状态方程为 ：

dp[i][k]+=dp[i-1][k-c[j]*w[i]];
 1 #include <set> 2 #include <map> 3 #include <list> 4 #include <cmath> 5 #include <ctime> 6 #include <deque> 7 #include <queue> 8 #include <stack> 9 #include <cstdio>10 #include <string>11 #include <vector>12 #include <cctype>13 #include <cstring>14 #include <sstream>15 #include <fstream>16 #include <cstdlib>17 #include <cassert>18 #include <iostream>19 #include <algorithm>20 using namespace std;21 int dp[21][15001];22 int main()23 {24     int n,m,k,c[21],w[21],i,j;25     scanf("%d%d",&n,&m);26     for(i=1; i<=n; i++)27         scanf("%d",&c[i]);28     for(i=1; i<=m; i++)29         scanf("%d",&w[i]);30     memset(dp,0,sizeof(dp));31     dp[0][7500]=1;32     for(i=1; i<=m; i++)33     {34         for(j=1; j<=n; j++)35         {36             for(k=c[j]*w[i];k<=15000;k++)37             {38                 dp[i][k]+=dp[i-1][k-c[j]*w[i]];39             }40         }41     }42     printf("%d\n",dp[m][7500]);43     return 0;44 }

 


联系
我们