当前位置:网站首页>4.22 study record (you only did water problems in one day, didn't you)
4.22 study record (you only did water problems in one day, didn't you)
2022-04-23 13:01:00 【Follow a r in the distance】
Originally I wanted to write a rolling array to optimize the record path qwq, It didn't come out
P1417 Cooking plan
Greedy optimization + knapsack
The problem was complicated at first , Looks like DP There's also DP( dynamic DP Dabao ), So I want to optimize it with greed , I bet that there is no case where the attenuation value is negative ( The longer it lasts, the more fragrant it becomes ) So we happily made it with backpacks
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define N 55
struct Obj
{
long long a,b,c;
};
Obj obj[N];
long long dp[N*100000];
bool cmp(Obj x,Obj y)
{
return x.c*y.b<y.c*x.b;
}
int main()
{
//freopen("in.txt","r",stdin);
long long t,n;
cin>>t>>n;
for(int i=1;i<=n;i++)
cin>>obj[i].a;
for(int i=1;i<=n;i++)
cin>>obj[i].b;
for(int i=1;i<=n;i++)
cin>>obj[i].c;
sort(obj+1,obj+n+1,cmp);
for(int i=1;i<=n;i++)
{
for(int j=t;j>=obj[i].c;j--)
{
dp[j]=max(dp[j],dp[j-obj[i].c]+obj[i].a-j*obj[i].b);
}
}
long long ans=-1;
for(int i=1;i<=t;i++)
{
ans=max(dp[i],ans);
}
cout<<ans<<endl;
return 0;
}
CF Div4 The topic ,, Although I feel there is nothing to sort out , Or write a H Let's write it down , After all, it's been a long time div4
H. Maximal AND
difficulty : Visual measurement 800
The question : For an array, you can choose one number at a time 30 Binary bits within bits 0 change 1,1 change 0, most k Time , Ask you the of the whole array & What is the maximum result of the operation
Ideas : Greedy for water
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
for(cin>>t;t;t--)
{
int n,k;
cin>>n>>k;
int a[40]={
0};
for(int i=1;i<=n;i++)
{
int tmp;
cin>>tmp;
for(int i=0;i<=30;i++)
a[i]++;
int con=0;
while(tmp)
{
if(tmp&1)
a[con]--;
con++;
tmp>>=1;
}
}
int ans=0;
for(int i=30;i>=0;i--)
{
if(a[i]<=k)
{
ans+=1<<i;
k-=a[i];
}
}
cout<<ans<<endl;
}
}
Today, after reviewing the tree backpack, I have a new understanding
1. Tree knapsack actually uses the idea of grouping knapsack
2. Tree backpacks usually have a situation
DFS(int now,int fath)
{
for(int i=head[now];i;i=edge[i].nex)
{
DP[now][1]=w[now];// Assign initial value to
DFS(edge[i].to,now);
for(int j=m+1;j>=1;j--)//m+1 Because virtual nodes are generated
{
for(int k=j-1;k>=0;k--)
{
dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[edge[i].to][k]);
}
}
}
}
3. Edges and points can be transformed into each other
版权声明
本文为[Follow a r in the distance]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204231257577274.html
边栏推荐
- Design and manufacture of 51 single chip microcomputer solar charging treasure with low voltage alarm (complete code data)
- Community version Alibaba MQ ordinary message sending subscription demo
- STM32 tracking based on open MV
- Design of body fat detection system based on 51 single chip microcomputer (51 + OLED + hx711 + US100)
- Free and open source agricultural Internet of things cloud platform (version: 3.0.1)
- Baserecyclerviewadapterhelper realizes pull-down refresh and pull-up loading
- 7_ The cell type scores obtained by addmodule and gene addition method are compared in space
- Introducing vant components on demand
- mysql8安装
- 22. Bracket generation
猜你喜欢
数据库中的日期时间类型
Remote access to raspberry pie at home (Part 1)
产品开发都应该知道的8个网站,增强工作体验
The quill editor image zooms, multiple rich text boxes are used on one page, and the quill editor upload image address is the server address
Servlet监听器&过滤器介绍
The accuracy and speed are perfectly balanced, and the latest image segmentation SOTA model is released!!!
three. JS text ambiguity problem
The El table horizontal scroll bar is fixed at the bottom of the visual window
进程虚拟地址空间区域划分
Record some NPM related problems (messy records)
随机推荐
Remote sensing image classification and recognition system based on convolutional neural network
7_Addmodule和基因加和法add 得到的细胞类型打分在空间上空转对比
Free and open source charging pile Internet of things cloud platform
Temperature and humidity monitoring + timing alarm system based on 51 single chip microcomputer (C51 source code)
The project file '' has been renamed or is no longer in the solution, and the source control provider associated with the solution could not be found - two engineering problems
STM32 is connected to the motor drive, the DuPont line supplies power, and then the back burning problem
如何实现点击一下物体播放一次动画
Design of body fat detection system based on 51 single chip microcomputer (51 + OLED + hx711 + US100)
7_ The cell type scores obtained by addmodule and gene addition method are compared in space
Go language: passing slices between functions
pyqt5 将opencv图片存入内置SQLlite数据库,并查询
CGC: contractual graph clustering for community detection and tracking
Three channel ultrasonic ranging system based on 51 single chip microcomputer (timer ranging)
[untitled] make a 0-99 counter, P1 7 connected to key, P2 connected to nixie tube section, common anode nixie tube, P3 0,P3. 1. Connect the nixie tube bit code. Each time you press the key, the nixie
Huawei cloud MVP email
[Blue Bridge Cup] April 17 provincial competition brushing training (the first three questions)
Process virtual address space partition
梳理网络IP代理的几大用途
Use of Presto date function
Connect orcale