当前位置:网站首页>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
边栏推荐
- 将opencv 图片转换为字节的方式
- SSM框架系列——数据源配置day2-1
- Ad20 supplementary note 3 - shortcut key + continuous update
- Custom nail robot alarm
- Golang realizes regular matching: the password contains at least one digit, letter and special character, and the length is 8-16
- 教你快速开发一个 狼人杀微信小程序(附源码)
- [vulnhub range] - DC2
- JMeter operation redis
- Go language slicing operation
- SQL exercise question 1
猜你喜欢
梳理網絡IP代理的幾大用途
将新增和编辑的数据同步更新到列表
Complete project data of UAV apriltag dynamic tracking landing based on openmv (LabVIEW + openmv + apriltag + punctual atom four axes)
4. DRF permission & access frequency & filtering & sorting
有趣的IDEA插件推荐,给你的开发工作增添色彩
Teach you to quickly develop a werewolf killing wechat applet (with source code)
SSM framework series - data source configuration day2-1
Customize classloader and implement hot deployment - use loadclass
melt reshape decast 长数据短数据 长短转化 数据清洗 行列转化
Object. The disorder of key value array after keys
随机推荐
软件测试周刊(第68期):解决棘手问题的最上乘方法是:静观其变,顺水推舟。
Complete project data of UAV apriltag dynamic tracking landing based on openmv (LabVIEW + openmv + apriltag + punctual atom four axes)
22. 括号生成
No idle servers? Import OVF image to quickly experience smartx super fusion community version
Use source insight to view and edit source code
将opencv 图片转换为字节的方式
Async void provoque l'écrasement du programme
SSM框架系列——数据源配置day2-1
Install nngraph
SSM framework series - JUnit unit test optimization day2-3
MySQL —— 16、索引的数据结构
Jupiter notebook installation
leetcode-791. Custom string sorting
云原生KubeSphere部署Redis
decast id.var measure.var数据拆分与合并
V-model binding value in El select, data echo only displays value, not label
产品开发都应该知道的8个网站,增强工作体验
Redis deployment of cloud native kubesphere
Process virtual address space partition
World Book Day: I'd like to recommend these books