poj1837【背包】
2024-09-08 08:44:23
题意:
有一根杆子,给出一些杆子上的位置,位置上能放重物,再给出一些重物的重量。
重物都需要被使用,但是位置不一定都要用到。
问你能有多少种方法让这个杆子平衡。
思路:
在位置上是0/1背包思想,取或不取。
dp[]直接代表在该重量下有多少方案数。
最大的重量是20*25*15=7500;
因为还有负数,我们就直接2*7500;
然后看一下dp[7500]就好了。
0/1背包思想,转化为对于前i个物品在j重量有多少方案,
对于钩子,直接for一遍放一遍,更新。
ps:如果dp数组要在一维上操作,那么每次更新都要使j变大或者变小,
那么我们枚举的时候就可以不会触碰到这次更新的结果。。然而太弱,搞不出一维的。
//#include<bits/stdc++.h>
#include<cstdio>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const double eps=1e-5;
const double pi=acos(-1.0);
const int mod=998244353;
const LL INF=0x3f3f3f3f;
const int N=25;
int dp[N][15007];
int a[N];
int b[N];
int main()
{
int t,i,k,j;
int c,g;
scanf("%d%d",&c,&g);
for(i=1;i<=c;i++)
scanf("%d",&a[i]);
for(i=1;i<=g;i++)
scanf("%d",&b[i]);
memset(dp,0,sizeof(dp));
dp[0][7500]=1;
for(i=1;i<=g;i++)
for(j=0;j<=15000;j++)
if(dp[i-1][j])
for(k=1;k<=c;k++)
dp[i][j+a[k]*b[i]]+=dp[i-1][j];
printf("%d\n",dp[g][7500]);
}
最新文章
- java之浮点数(笔记)
- WCF多种调用方式兼容
- codeforces Round #258(div2) D解题报告
- SharePoint中 服务器发出意外响应。响应状态代码是";500";。
- Unity 碰撞器和触发器的理解
- VR全景:实体店与互联网的完美结合
- mysql常见的优化方法
- IDEA安装和JDK的配置
- ipv6地址配置实验(GNS3/ENSP)
- mysql第一课,数据库的简单简单操作方法(配图略虐狗)
- Out of range value for column ";";
- python提取文件中的方法名称
- Linux安装Tomcat-Nginx-FastDFS-Redis-Solr-集群——【第九集之安装Tomcat+Nginx反向代理Tomcat集群】
- [11]Windows内核情景分析---设备驱动
- Mysql配置参数sync_binlog说明
- ZOOKEEPER解惑[转]
- STL_iterator返回值
- CentOS 静态IP设置&;修改网卡名
- 微服务Kong(七)——CLI参考
- 巧用渐变色打造精致移动端APP