BZOJ 2281 消失之物
2024-08-27 22:26:34
ftiasch 有 N 个物品, 体积分别是 W1, W2, …, WN。 由于她的疏忽, 第 i 个物品丢失了。 “要使用剩下的 N – 1 物品装满容积为 x 的背包,有几种方法呢?” — 这是经典的问题了。她把答案记为 Count(i, x) ,想要得到所有1 <= i <= N, 1 <= x <= M的 Count(i, x) 表格。
Input
第1行:两个整数 N (1 ≤ N ≤ 2 × 103) 和 M (1 ≤ M ≤ 2 × 103),物品的数量和最大的容积。
第2行: N 个整数 W1, W2, …, WN, 物品的体积。
Output
一个 N × M 的矩阵, Count(i, x)的末位数字。
Sample Input
3 2
1 1 2
Sample Output
11
11
21
HINT
如果物品3丢失的话,只有一种方法装满容量是2的背包,即选择物品1和物品2。
题解
如果每次都去掉一个并跑背包,时间复杂度为O(mn^2),会T。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
int n,m,dp[MAXN];
int a[MAXN];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++){
memset(dp,0,sizeof(dp));
dp[0]=1;
for(register int j=1;j<=n;j++){
if(i==j) continue;
for(register int k=m;k>=a[j];k--){
dp[k]+=dp[k-a[j]];
dp[k]%=10;
}
}
for(register int j=1;j<=m;j++)
printf("%d",dp[j]%10);
printf("\n");
}
return 0;
}
下面我们说正解,其实也不是那么难想
对于每个i只要`
for(register int j=a[i];j<=m;j++){
g[j]-=g[j-a[i]];
g[j]=(g[j]+10)%10;
}`
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
int n,m,dp[MAXN],g[MAXN];
int a[MAXN],cnt[MAXN][MAXN];
bool vis[MAXN];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
dp[0]=1;
for(int i=1;i<=n;i++)
for(register int k=m;k>=a[i];k--){
dp[k]+=dp[k-a[i]];
dp[k]%=10;
}
for(int i=1;i<=n;i++){
memcpy(g,dp,sizeof(g));
for(register int j=a[i];j<=m;j++){
g[j]-=g[j-a[i]];
g[j]=(g[j]+10)%10;
}
for(register int j=1;j<=m;j++)
printf("%d",g[j]%10);
printf("\n");
}
return 0;
}
最新文章
- Asp.net MVC5 路由Html后缀的问题
- Yii的学习(1)--安装配置
- Linux--U盘安装Ubuntu12.04
- spring 定时任务标注
- POJ 3580:SuperMemo(Splay)
- Linux中“新旧”TCP/IP工具的对比
- 矩阵-DirectX与OpenGL的不同
- Oracle基础<;5>;--触发器
- SQL查询性能分析之(not in)、(and not)、()、(!=)性能比较
- jQuery UI 日期控件--datepicker
- 11.java.lang.ArrayStoreException
- Linux 任务控制(bg job fg nohup &;)
- [PHP源码阅读]number_format函数
- css学习の第一弹—格式创建
- 详解MariaDB数据库的事务
- Python进程池Pool
- Java反射实现原理分析
- java operate
- 【Python基础】zip函数的使用
- tomcat2章2
热门文章
- 【JUC】JDK1.8源码分析之AbstractQueuedSynchronizer
- Python生成Windows可执行exe文件
- 3.4_springboot2.x整合spring Data Elasticsearch
- Js_案例(电灯)
- Tomcat Geoserver等服务器 端口号修改
- OC和Cocos-js的互相调用
- SPN扫描利用
- 神经网络 (2)- Alexnet Training on MNIST
- Java 多线程 - 锁的类型
- System.Web.Mvc.HttpPatchAttribute.cs