首页 > 代码库 > POJ 1837 Balance

POJ 1837 Balance

题意:给你C个挂钩,W个钩码,要你能使一个天平平衡

数据解释:

2 4	
-2 3 
3 4 5 8
以原点为支点,那么-2代表支点左边2处有一个钩码,同理3代表右边的点

所以案例数据有一个成立的例子是(3+5)*3=(4+8)*2或是(3+4+5)*2=8*3(力臂平衡)

有2种情况所以输出2;

思路:这个如果不是按照题目的分类说是DP我还想不到这个思路,我感觉我进步挺大了,能独立推出转移方程了。

首先我们看这道题首先是要求力平衡,那么一个限制是重量。与力相关的有钩码与挂钩的位置。显然,钩码可以放在任一位置,那么我们此时的状态可以为钩码的数量  与当前的力臂。钩码最大数为20,力臂为15*25*20=7500,以7500为支点,所以最大为15000


所以我们可以考虑在当前放了i-1个钩码时,它的力臂为j,放法有dp[i-1][j]种。那么放第i个钩码时在任一位置也有dp[i-1][j]种放法即dp[i][j+w[i]*c[位置]]

所以AC代码如下:

#include<stdio.h>
#include<string.h>
int dp[25][15000];
int c[25],w[25];
int main()
{
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        int i,j;
        for(i=1;i<=n;i++)
            scanf("%d",&c[i]);
        for(i=1;i<=m;i++)
            scanf("%d",&w[i]);
        memset(dp,0,sizeof(dp));
        dp[0][7500]=1;
        for(i=1;i<=m;i++)
            for(j=1;j<=15000;j++)
            if(dp[i-1][j])
            {
                for(int k=1;k<=n;k++) //每个位置都需要枚举出来
                    dp[i][j+c[k]*w[i]]+=dp[i-1][j];
            }
        printf("%d\n",dp[m][7500]); //支点
    }
    return 0;
}