当前位置:网站首页>2/13 review Backpack + monotonic queue variant
2/13 review Backpack + monotonic queue variant
2022-07-06 04:05:00 【Zhong Zhongzhong】
Looking back on these backpacks and greed , It's much simpler ……qaq
ordinary 01 Knapsack for the number of solutions :
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e4+5;;
int v,n,a[30],f[maxn];
signed main()
{
scanf("%lld%lld",&v,&n);
for(int i=1;i<=v;i++)
scanf("%lld",&a[i]);
f[0]=1;
for(int i=1;i<=v;i++)
{
for(int j=a[i];j<=n;j++)
f[j]=f[j]+f[j-a[i]];
}
cout<<f[n]<<endl;
return 0;
}
https://www.luogu.com.cn/problem/P1586
One more dimension is added : Several numbers are used to form this result
f[i][j]: Representation number i It was used j The number makes up
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+5;
const int M=32768;
int t,n,f[maxn][5];
signed main()
{
f[0][0]=1;
for(int i=1;i*i<=M;i++)
{
for(int j=i*i;j<=M;j++)
{
for(int k=1;k<=4;k++)
f[j][k]+=f[j-i*i][k-1];
}
}
scanf("%lld",&t);
while(t--)
{
int n,tmp=0;
scanf("%lld",&n);
for(int i=1;i<=4;i++)
tmp+=f[n][i];
cout<<tmp<<endl;
}
return 0;
}
https://www.luogu.com.cn/problem/P1638
Constantly update the value of the left endpoint , If the last position of the left endpoint is greater than the left endpoint , be left++
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e6+5;
const int inf=0x3f3f3f3f;
int pos[2005],p[maxn],n,m,k;
signed main()
{
scanf("%lld%lld",&n,&m);
memset(pos,-1,sizeof(pos));
int l=1,ll=0,rr=0,ml=inf;
for(int i=1;i<=n;i++)
{
scanf("%lld",&p[i]);
if(pos[p[i]]==-1)
k++;
pos[p[i]]=i;
while(l!=i&&l<pos[p[l]])
l++;
if(k==m&&i-l+1<ml)
{
ml=i-l+1;
ll=l;
rr=i;
}
}
//cout<<ml<<endl;
cout<<ll<<" "<<rr<<endl;
return 0;
}
边栏推荐
- MySQL about self growth
- How to execute an SQL statement in MySQL
- Simple blog system
- After five years of testing in byte, I was ruthlessly dismissed in July, hoping to wake up my brother who was paddling
- 使用JS完成一个LRU缓存
- 10个 Istio 流量管理 最常用的例子,你知道几个?
- mysql关于自增长增长问题
- Exchange bottles (graph theory + thinking)
- C#(三十)之C#comboBox ListView treeView
- MySQL transaction isolation level
猜你喜欢
Yyds dry goods inventory web components series (VII) -- life cycle of custom components
【FPGA教程案例11】基于vivado核的除法器设计与实现
阿里测试师用UI自动化测试实现元素定位
在字节做测试5年,7月无情被辞,想给划水的兄弟提个醒
MySQL about self growth
Stc8h development (XII): I2C drive AT24C08, at24c32 series EEPROM storage
STC8H开发(十二): I2C驱动AT24C08,AT24C32系列EEPROM存储
在 .NET 6 中使用 Startup.cs 更简洁的方法
[adjustable delay network] development of FPGA based adjustable delay network system Verilog
【按鍵消抖】基於FPGA的按鍵消抖模塊開發
随机推荐
【FPGA教程案例11】基于vivado核的除法器设计与实现
Differential GPS RTK thousand search
《2022年中国银行业RPA供应商实力矩阵分析》研究报告正式启动
C (XXIX) C listbox CheckedListBox Imagelist
Take you to wechat applet development in 3 minutes
STC8H开发(十二): I2C驱动AT24C08,AT24C32系列EEPROM存储
asp. Core is compatible with both JWT authentication and cookies authentication
Global and Chinese market of aircraft anti icing and rain protection systems 2022-2028: Research Report on technology, participants, trends, market size and share
绑定在游戏对象上的脚本的执行顺序
Custom event of C (31)
In Net 6 CS more concise method
【FPGA教程案例12】基于vivado核的复数乘法器设计与实现
C#(二十八)之C#鼠标事件、键盘事件
[optimization model] Monte Carlo method of optimization calculation
Pandora IOT development board learning (HAL Library) - Experiment 9 PWM output experiment (learning notes)
Global and Chinese markets for patent hole oval devices 2022-2028: Research Report on technology, participants, trends, market size and share
[FPGA tutorial case 12] design and implementation of complex multiplier based on vivado core
阿里测试师用UI自动化测试实现元素定位
Interface idempotency
C mouse event and keyboard event of C (XXVIII)