注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2022]Pku1837 Balance  

2015-01-29 11:05:56|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2022: Pku1837 Balance

Time Limit: 5 Sec  Memory Limit: 64 MB
Submit: 209  Solved: 90
[Submit][Status]

Description

Gigel has a strange "balance" and he wants to poise it. Actually, the device is different from any other ordinary balance. It orders two arms of negligible weight and each arm's length is 15. Some hooks are attached to these arms and Gigel wants to hang up some weights from his collection of G weights (1 <= G <= 20) knowing that these weights have distinct values in the range 1..25. Gigel may droop any weight of any hook but he is forced to use all the weights. Finally, Gigel managed to balance the device using the experience he gained at the National Olympiad in Informatics. Now he would like to know in how many ways the device can be balanced. Knowing the repartition of the hooks and the set of the weights write a program that calculates the number of possibilities to balance the device. It is guaranteed that will exist at least one solution for each test case at the evaluation. 输入一个天平若干(<=20)挂钩的位置,将若干(<=20)砝码挂到天平上,问有多少种使天平挂平衡的方法。

Input

The input has the following structure: ? the first line contains the number C (2 <= C <= 20) and the number G (2 <= G <= 20); ? the next line contains C integer numbers (these numbers are also distinct and sorted in ascending order) in the range -15..15 representing the repartition of the hooks; each number represents the position relative to the center of the balance on the X axis (when no weights are attached the device is balanced and lined up to the X axis; the absolute value of the distances represents the distance between the hook and the balance center and the sign of the numbers determines the arm of the balance to which the hook is attached: '-' for the left arm and '+' for the right arm); ? on the next line there are G natural, distinct and sorted in ascending order numbers in the range 1..25 representing the weights' values.

Output

The output contains the number M representing the number of possibilities to poise the balance.

Sample Input

2 4
-2 3
3 4 5 8

Sample Output

2

HINT

第一种放法把(4,8)放左边,(3,5)放右边
第二种放法把((3,4,5)放左边,8单独放右边

Solution

首先很容易想到枚举的方法,即把所有钩子放在所有位置的情况全部枚举一遍。然后统计使天平平衡的方案总数。但显然会超时。

再进一步分析题目,可以发现砝码与砝码之间是互不干扰的。也就是说放每个砝码是独立的,放一个砝码不会影响下一个砝码的放置。这容易让我们想到一类背包问 题:求将若干个物品放到指定容积的背包中的方案数。因为它们同样求方案数,放物品时同样互不干扰。而不同的地方是背包问题每个物品有一个体积,且背包有容 积。

我们知道天平平衡的条件是:左侧每个物品质量与离中心距离的乘积之和,等于右侧。若我们把一个重量为w的砝码放在坐标为x的钩子上,那么对天平的影响是 w*x。如果x是带符号的话,那么砝码放在左右两侧就都可以由w*x统一起来。即所有的w*x之和为0时,天平平衡。

这时候我们发现可以把0作为背包的容积,而w*x看做物品的体积。这样题目就可以转换为一个背包问题:现有g类物品(对应砝码),每类物品有c种不同的体 积(对应钩子,体积可为负值),现在要从每类物品中挑出一个,使它们的体积之和为0,求方案数。这样显然就可以用动态规划解决了。用F[I,J]表示已经 放了前I个砝码,达到影响值J的方案数,则:F[I,J]=F[I,J]+F[I-1,J-w[i]*x[k]](其中1<=k<=c,表示 放在第k个钩子上)。最终答案为F[g,0]。

Code

/**************************************************************
    Problem: 2022
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:160 ms
    Memory:1116 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#include<algorithm>
int c,g,i,j,k,a[30],x,con=10000,v;long long min,max,b[2][20000];
int main(){
    for(scanf("%d%d",&c,&g),i=1;i<=c;i++)scanf("%d",&a[i]);
    std::sort(a+1,a+1+c);
    for(scanf("%d",&x),i=1;i<=c;i++)b[0][a[i]*x+con]=1;
    for(min=a[1]*x,max=a[c]*x,j=1;j<g;j++){
        memset(b[j&1],0,sizeof(b[j&1]));
        for(scanf("%d",&x),i=1;i<=c;i++)
        for(v=x*a[i],k=min;k<=max;k++)
        b[j&1][k+v+con]+=b[~j&1][k+con];
        min+=a[1]*x,max+=a[c]*x;
    }
    printf("%lld\n",b[~j&1][con]);
}
  评论这张
 
阅读(39)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018