loj6089 小 Y 的背包计数问题
2024-09-01 08:08:19
吐槽:
好吧开学了果然忙得要死……不过为了证明我的blog还没有凉,还是跑来更一波水题
题意:
有n种物品,第i种体积为i,问装满一个大小为n的背包有多少种方案?
$n\leq 10^5.$
做法:
这种题一看就很想按根号分类是不是……
设阈值大小为$m=\sqrt n$,对于体积$\leq m$的所有物品,直接跑多重背包:
f[i][j]表示前i个物品,体积和为j的方案数,$f[i][j]=\sum f[i-1][j-ki],k\in [0,i]$。
记录sum[x]表示$\sum f[i-1][j]$其中$j\% i=x$,同时需满足当前的j和上一个状态lastj的差$\leq i^2$。这样可以把dp优化到$\mathcal{O}(n\sqrt n)$。
对于体积$>m$的所有物品,由于$i^2$一定$>n$,所以相当于完全背包:
但是当然不能直接跑完全背包,复杂度是炸的。可以发现物品的个数不超过$\sqrt n$,那么
g[i][j]表示i个物品,体积和为j的方案数(注意和f的区别),$g[i][j]=g[i][j-i]+g[i-1][j-m-1]$。
具体来说这个转移表示,要么把当前i个物品每个体积都增加1,要么插入一个体积为m+1的物品(一个构造法,恰好不重不漏地计算了所有方案)。
复杂度也是$\mathcal{O}(n\sqrt n)$。
最后把两者乘法原理合并起来即可。
题外话:51nod1259是一道类似的题,区别是它都是完全背包,更简单了些。
code:
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
#define ll long long
using namespace std;
#define N 100005
const int mod=;
int n,m,f[][N],sum[N],g[][N],now,t,ans;
void upd(int &x,int y){x+=y;x-=x>=mod?mod:;}
int main(){
cin>>n;m=sqrt(n);now=;f[][]=;
rep (i,,m){//f[i][j]:前i个体积<=m的物品,体积和为j的方案数
now^=;memset(sum,,sizeof(sum));
rep (j,,n){
upd(f[now][j]=f[now^][j],sum[j%i]);upd(sum[j%i],f[now^][j]);
if (j>=i*i) upd(sum[j%i],mod-f[now^][j-i*i]);
}
}
ans=f[now][n];t=now;
g[][]=;now=;
rep (i,,m){//g[i][j]:i个体积都>m的物品,体积和为j的方案数
now^=;memset(g[now],,sizeof(g[now]));
rep (j,i,n){
upd(g[now][j],g[now][j-i]);
if (j>=m+) upd(g[now][j],g[now^][j-m-]);
}
rep (i,,n) upd(ans,(ll)f[t][i]*g[now][n-i]%mod);
}
cout<<ans;
return ;
}
最新文章
- Atitit java集成内嵌浏览器与外嵌浏览器attilax总结
- SQL Server 迁移数据到MySQL
- android应用安全——(数据抓包)跟踪监控android数据包
- swift 构建类
- C# 获得MP4时长
- netcore 控制台中文乱码
- php构造函数和析构函数
- BizTalk开发系列(三十四) Xpath
- 关于点击ztree的节点将页面生成到easyui的新增选项卡(easyui-tabs)时,总是在浏览器中生成一个新的页面的问题
- hud1166 敌兵布阵
- PHP+mysql统计排名第几位
- mysql 建立索引的原则
- Matlab实现PCA
- Provably Delay Efficient Data Retrieving in Storage Clouds---INFOCOM 2015
- 联发科安卓6.0项目的到来的第一个难题:tar的分包与并包
- sql server 按年月日分组
- jmeter脚本录制的两种方式
- 个人总结-----非贪心算法的图的m着色判断及优化问题
- 什么是API测试
- 【SSH网上商城项目实战16】Hibernate的二级缓存处理首页的热门显示
热门文章
- 关于runOnUiThread()与Handler两种更新UI的方法
- HTML5学习--SVG全攻略(基础篇)
- tensorflow session 和 graph
- web性能优化之js图片懒加载
- ASP .Net Core系统部署到SUSE 16 Linux Enterprise Server 12 SP2 64 具体方案
- java基础68 JavaScript城市联动框(网页知识)
- 洛谷P3760异或和
- ubuntu和windows双系统启动顺序的修改
- Kubernetes 概述和搭建(多节点)
- CVE-2013-2729 Adobe Reader和Acrobat 数字错误漏洞