POJ1837 [DP水题]_它有两条重量可以忽略的臂,每条臂的长度是15。臂上有一些挂钩,gigel想要从他拥有-程序员宅基地

技术标签： 动态规划入门  

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. 

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


题意：有一个天平，左臂右臂各长15，然后给出n，m，n代表有几个挂钩，挂钩给出负数代表在左臂的距离，正数则在右臂
m代表有m个砝码，要你求出使得这个天平保持平衡有几种方法，要求所有砝码全部使用完
 
思路：首先我们先要明确dp数组的作用，dp[i][j]中，i为放置的砝码数量，j为平衡状态，0为平衡,j<0左倾，j>0右倾，由于j作为下标不能是负数，所以我们要找一个新的平衡点，因为15*20*20 = 7500，所以平衡点设置为7500,
然后我们可以得出动态方程 dp[i][j+w[i]*c[k])+=dp[i-1][j];
  1. #include<cstring>
  2. #include<iostream>  
  3. using namespace std;  
  4.   
  5. int dp[21][15001]; //状态数组dp[i][j]  
  6.                        //放入（挂上）前i个物品（钩码）后，达到j状态的方法数  
  7. int main(int i,int j,int k)  
  8. {  
  9.     int n;  //挂钩数  
  10.     int g;  //钩码数  
  11.     int c[21];  //挂钩位置  
  12.     int w[21];  //钩码重量  
  13.   
  14.       
  15.     /*Input*/  
  16.   
  17.     cin>>n>>g;  
  18.   
  19.     for(i=1;i<=n;i++)  
  20.         cin>>c[i];  
  21.     for(i=1;i<=g;i++)  
  22.         cin>>w[i];  
  23.   
  24.     /*Initial*/  
  25.   
  26.     memset(dp,0,sizeof(dp));  //达到每个状态的方法数初始化为0  
  27.     dp[0][7500]=1;     //7500为天枰达到平衡状态时的平衡度  
  28.                        //放入前0个物品后，天枰达到平衡状态7500的方法有1个，就是不挂钩码  
  29.   
  30.     /*DP*/  
  31.   
  32.     for(i=1;i<=g;i++)  
  33.         for(j=0;j<=15000;j++)  
  34.             if(dp[i-1][j])  //优化，当放入i-1个物品时状态j已经出现且被统计过方法数，则直接使用统计结果  
  35.                             //否则忽略当前状态j  
  36.                 for(k=1;k<=n;k++)  
  37.                     dp[i][ j+w[i]*c[k] ] += dp[i-1][j]; //状态方程  
  38.       
  39.     /*Output*/  
  40.   
  41.     cout<<dp[g][7500]<<endl;  
  42.     return 0;  
  43. }
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/qq_39996728/article/details/79935935

智能推荐

15.Mybatis 更新操作-update_update mybatis-程序员宅基地

文章浏览阅读7.5w次，点赞17次，收藏37次。1. update 标签update 标签是用于定义更新 语句的.1.1 常用属性update 有几个常用的属性, 但是通常只需要设置id 即可.id: sql 片段在命名空间内的唯一标识. 和mapper 中方法名保持一致parameterType: 参数类型, 通常都可以省略.flushCache: 是否刷新(清空)一级缓存和二级缓存, 默认为true. 笔者尝试设置为false..._update mybatis

android bitmap 保存到本地_Android全屏截图的方法，返回Bitmap并且保存在SD卡上-程序员宅基地

文章浏览阅读208次。今天做分享，需求是截图分享，做了也是一个运动类的产品，那好，我们就直接开始做，考虑了一下，因为是全屏的分享，所有很自然而然的想到了View的getDrawingCache()方法来获取Bitmap，看到网上有人说截取不了WebView上的图片，倒是没有去尝试，因为我们的应用不需要，不过有时间还是要去试试，占占坑，这篇博客只是记录一下知识点，没什么技术含量我们写个小Sample就好了activity..._net android.graphics.bitmap 保存

token与cookie区别_token和cookie的区别-程序员宅基地

文章浏览阅读1.2k次。总而言之，Token 和 Cookie 在身份验证和授权方面都有其特定的用途和优势。选择使用哪种机制取决于具体的应用场景和安全需求。_token和cookie的区别

微信公众号一、接入微信并实现机器人自动回复功能_glm 微信云托管 公众号 微信机器人-程序员宅基地

文章浏览阅读2.6k次。一、说明微信公众平台https://mp.weixin.qq.com/cgi-bin/loginpage?t=wxm2-login&lang=zh_CN测试平台https://mp.weixin.qq.com/debug/cgi-bin/sandbox?t=sandbox/login本文demo链接：https://pan.baidu.com/s/1syGGvdCJqcSPnZ..._glm 微信云托管 公众号 微信机器人

PTA 6-4 重写父类方法equals (5分)-程序员宅基地

文章浏览阅读6.4k次，点赞2次，收藏11次。6-4 重写父类方法equals (5分)在类Student中重写Object类的equals方法。使Student对象学号(id)相同时判定为同一对象。函数接口定义：在类Student中重写Object类的equals方法。使Student对象学号(id)相同时判定为同一对象。裁判测试程序样例：class Student { int id; String name; i..._6-4 重写父类方法equals

GridView的PagerTemplate分页-程序员宅基地

文章浏览阅读55次。Code<asp:GridViewID="gvProject"runat="server"BorderColor="Gray"Height="20px"Width="98%"AllowPaging="True"AutoGenerateColumns="False"EmptyDataText="没有符合查询条件的数据！"OnDataBound="gvProject..._ystem.web.ui.webcontrols.templatefield”不具有名为“pagertemplate”的公共属

随便推点

“Unknown initial character set index '255' received from serve”错误解决过程 - Mybatis 示例_unknown initial character 255-程序员宅基地

文章浏览阅读4.7k次，点赞8次，收藏13次。今天在学习Mybaits的时候，根据教程写出了一个第一个程序——从数据库读取一条数据并打印。当一切都就绪了：user.javaUserMapper.xmlmybatis-config.xml测试类依葫芦画瓢地写下来，以为没问题了，运行这个测试方法，竟然报错了：org.apache.ibatis.exceptions.PersistenceException: ### Err..._unknown initial character 255

[附源码]JAVA+ssm校友信息管理系统（程序+Lw)_java校友信息管理系统-程序员宅基地

文章浏览阅读307次。项目运行环境配置：Jdk1.8 + Tomcat7.0 + Mysql + HBuilderX（Webstorm也行）+ Eclispe（IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持）。项目技术：SSM + mybatis + Maven + Vue 等等组成，B/S模式 + Maven管理等等。环境需要1.运行环境：最好是java jdk 1.8，我们在这个平台上运行的。其他版本理论上也可以。2.IDE环境：IDEA，Eclipse,Myeclipse都可以。推荐IDEA;_java校友信息管理系统

linux网络编程之socket编程(三)-程序员宅基地

文章浏览阅读94次。今天继续对socket编程进行学习，在学习之前，需要回顾一下上一篇中编写的回射客户/服务器程序(http://www.cnblogs.com/webor2006/p/3923254.html)，因为今天的知识点需要基于它来进行说明，下面来回顾一下关键代码:对于服务器端：echosrv.c对于客户端：echocli.c下面通过一个简单的图来描述一下其关系：可想而知，这两个套接字都有..._if (connect(sock, (struct sockaddr*)(&addr), sizeof(addr))

magic4.0跟harmonyos,支持升级Harmony 2.0 Magic UI 4.0 9月中旬招募公测-程序员宅基地

文章浏览阅读1.4k次。Magic UI 4.0系统将于9月中旬开始招募公测，适配荣耀30系列以及荣耀V30系列产品，后续同样支持升级为HarmonyOS 2.0系统。【PChome手机频道资讯报道】9月10日，华为开发者大会(HDC 2020)正式召开，正式推出HarmonyOS 2.0与EMUI 11操作系统。与此同时，荣耀在微博官宣，Magic UI 4.0系统也将于9月中旬开始招募公测，Magic UI 4.0广..._magicui4什么时候升的

关于启动报错：Field xxxMapper in com.xxx.service.impl.xxxServiceImpl required a bean of type的解决方案_field teachermapper in com.example.itextdemo.servi-程序员宅基地

文章浏览阅读3w次，点赞14次，收藏8次。检测你的启动类Application的MapperScan注解扫描是否配置正确！_field teachermapper in com.example.itextdemo.service.impl.eduteacherservicei

win7成功下编译VLC1.0.5-程序员宅基地

文章浏览阅读64次。想用最新版本的VLC 于是编译1.0.5版本由于有了前面的基础只需要以下几步就OK：关于修改1. 很多人提示的修改libtool第144行。--我的144行不是blank ，so没有更改；22) 注释掉Makefile.am第697，727，738行，就是行首加入#。#cp "$(top_srcdir)/extras..._vlc-1.0.5-win32.exe

推荐文章

热门文章

相关标签