当前位置:网站首页>Acwing - the collection of pet elves - (multidimensional 01 Backpack + positive and reverse order + two forms of DP for the answer)
Acwing - the collection of pet elves - (multidimensional 01 Backpack + positive and reverse order + two forms of DP for the answer)
2022-07-05 07:45:00 【Lovely and beautiful girl】
The question :
There is n A pet , Catch them to a Physical strength and b Spirit ball of . Now you have m physical strength ,k An elf ball . Ask how many pets you can catch at most , Then when there are most pets , How much physical strength is left at most .
reflection :
Obviously, this can also optimize the dimension of enumerating items . Then triple cycle is ok . For enumeration h When , Reverse order and positive order are the same , Because the last layer m It's in reverse order , therefore h Even positive order , He also uses the upper layer every time , Not on this floor . If there is 4 Layer circulation , equally , Just one layer in reverse order . For those who require the most pets , Highest physical strength . Then just enumerate directly , Find out more pets , If the same, then look at the least physical use . although dp The definition of , I can't directly ask how much physical strength I can have left , But you can ask how much physical strength you used, right .
The second way , It's the gold coin title of the robot competition before . For example, the classic backpack volume and value , Just exchange the power of value and volume , Let what you ask be what you maintain , The result is known , Finally, enumerate and judge dp Whether the status inside meets the given limit is ok . So this question can define the state dp[i][j], Not more than i HP , Captured j A pet , At least how many elf balls should be used . Then finally enumerate all the States , See if < The number of ELF balls , If you can, you can update the answer . The same is true dp[i][j] Defined as , No more than i Spirit ball of , Captured j A pet , How much physical strength should be used at least . Then do the same .
How to determine the state
Namely :
1. Put the required answer , Become dp The answer , This is the most common way .
2. Put the required answer , Put it in dp In the defined state , and dp The answer is a known condition .
For how to define the state , It depends on the scope of each limitation , See how many cycles you can use at least , Try to choose the one with the best time complexity . But we must ensure that there is an optimal substructure to deal with .
Another thing worth noting is , Generally, the first dimension enumeration items are optimized ,dp The state of is the value of the upper layer every time , So don't consider not choosing i The emptying of this item . Actually, I have considered . But if it is not optimized , Then you have to go , Otherwise, there will be less updates . It must be from 1 To m All have to enumerate , Can't fall .
Not more than j Spirit ball and not super k Physical strength , How many pets can you catch at most .
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int mod = 1e9+7,inf = 1e9;
const int N = 2e5+10,M = 2010;
int T,n,m,k,h;
PII va[110];
int dp[1010][510];
signed main()
{
IOS;
cin>>m>>h>>n;
for(int i=1;i<=n;i++) cin>>va[i].fi>>va[i].se;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=1;j--)
{
for(int k=1;k<=h;k++)
{
if(j>=va[i].fi&&k>=va[i].se)
dp[j][k] = max(dp[j][k],dp[j-va[i].fi][k-va[i].se]+1);
}
}
}
int maxn = 0,sum = 0;
for(int k=0;k<h;k++)
{
if(maxn<dp[m][k])
{
maxn = dp[m][k];
sum = h-k;
}
else if(maxn==dp[m][k]) sum = max(sum,h-k);
}
cout<<maxn<<" "<<sum<<"\n";
return 0;
}
Not more than j Physical strength and grasp k Our pet , At least how many elf balls to use .
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int mod = 1e9+7,inf = 1e9;
const int N = 2e5+10,M = 2010;
int T,n,m,k,h;
PII va[110];
int dp[510][110];
signed main()
{
IOS;
cin>>m>>h>>n;
for(int i=1;i<=n;i++) cin>>va[i].fi>>va[i].se;
mem(dp,0x3f);
for(int i=0;i<=h;i++) dp[i][0] = 0;
for(int i=1;i<=n;i++)
{
for(int j=h;j>=1;j--)
{
for(int k=1;k<=n;k++)
{
if(j>=va[i].se)
dp[j][k] = min(dp[j][k],dp[j-va[i].se][k-1]+va[i].fi);
}
}
}
int maxn = -inf,sum = 0;
for(int i=0;i<h;i++)
{
for(int j=0;j<=n;j++)
{
if(dp[i][j]<=m)
{
if(maxn<j)
{
maxn = j;
sum = h-i;
}
else if(maxn==j) sum = max(sum,h-i);
}
}
}
cout<<maxn<<" "<<sum<<"\n";
return 0;
}
Not more than j The elf ball and caught k Our pet , How much physical strength should we use at least .
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int mod = 1e9+7,inf = 1e9;
const int N = 2e5+10,M = 2010;
int T,n,m,k,h;
PII va[110];
int dp[1010][110];
signed main()
{
IOS;
cin>>m>>h>>n;
for(int i=1;i<=n;i++) cin>>va[i].fi>>va[i].se;
mem(dp,0x3f);
for(int i=0;i<=m;i++) dp[i][0] = 0;
for(int i=1;i<=n;i++)
{
for(int j=m;j>=1;j--)
{
for(int k=1;k<=n;k++)
{
if(j>=va[i].fi)
dp[j][k] = min(dp[j][k],dp[j-va[i].fi][k-1]+va[i].se);
}
}
}
int maxn = -inf,sum = 0;
for(int i=0;i<=m;i++)
{
for(int j=0;j<=n;j++)
{
if(dp[i][j]<h)
{
if(maxn<j)
{
maxn = j;
sum = h-dp[i][j];
}
else if(maxn==j) sum = max(sum,h-dp[i][j]);
}
}
}
cout<<maxn<<" "<<sum<<"\n";
return 0;
}
Robot gold coin topic :
reflection :
If you follow the normal way of thinking, it is dp[i][j] Before use i Card roll , No more than j Time for , How many gold coins can you get at most . But such a double cycle must have timed out . But the scope of finding gold coins is very small . therefore dp[i][j] Defined as before i Card roll , Get no more than j Gold coins , At least how much time . Finally, just enumerate the answer of gold coin , On the premise that the time does not exceed the conditions .
Code :
2D version :
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;
int T,n,m,k;
PII va[N];
int dp[1010][30010];
signed main()
{
IOS;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>va[i].fi;
for(int i=1;i<=n;i++) cin>>va[i].se;
int R = n*30;
mem(dp,0x3f);
for(int i=0;i<=n;i++) dp[i][0] = 0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=R;j++)
{
dp[i][j] = min(dp[i][j],dp[i-1][j]); // Note that this is a double cycle. You can't throw it away , If you optimize a single loop , Then itself is already on the next level , So don't write anymore , But it needs to be updated here . It must be from 1 To R, Cannot from va[i].se Start , Because there will be less .
if(j>=va[i].se)
dp[i][j] = min(dp[i][j],dp[i-1][j-va[i].se]+va[i].fi);
}
}
int maxn = 0;
for(int i=1;i<=R;i++)
{
if(dp[n][i]<=m)
maxn = max(maxn,i);
}
cout<<maxn;
return 0;
}
One dimensional version :
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;
int T,n,m,k;
PII va[N];
int dp[30010];
signed main()
{
IOS;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>va[i].fi;
for(int i=1;i<=n;i++) cin>>va[i].se;
int R = n*30;
mem(dp,0x3f);
dp[0] = 0;
for(int i=1;i<=n;i++)
{
for(int j=R;j>=va[i].se;j--) // because dp Itself is the upper layer , So here from va[i].se It's okay at first .
dp[j] = min(dp[j],dp[j-va[i].se]+va[i].fi);
}
int maxn = 0;
for(int i=1;i<=R;i++)
{
if(dp[i]<=m)
maxn = max(maxn,i);
}
cout<<maxn;
return 0;
}
summary :
Think more , Understand the essence of Algorithm .
边栏推荐
- Web page Chinese display (print, etc.) GBK error, solution, software
- Eclipse project recompile, clear cache
- CADD课程学习(5)-- 构建靶点已知的化合结构(ChemDraw)
- .NET服务治理之限流中间件-FireflySoft.RateLimit
- STM32 knowledge points
- Play with grpc - go deep into concepts and principles
- Apple system shortcut key usage
- RTOS in the development of STM32 single chip microcomputer
- Function and usage of function pointer
- mysql 盲注常见函数
猜你喜欢
Numpy——1. Creation of array
借助 Navicat for MySQL 软件 把 不同或者相同数据库链接中的某数据库表数据 复制到 另一个数据库表中
软件设计师:03-数据库系统
I 用c I 实现队列
Detailed explanation of miracast Technology (I): Wi Fi display
Self summary of college life - freshman
Openxlsx field reading problem
With the help of Navicat for MySQL software, the data of a database table in different or the same database link is copied to another database table
万字详解八大排序 必读(代码+动图演示)
Application of ultra pure water particle counter in electronic semiconductors
随机推荐
Play with grpc - go deep into concepts and principles
Build your own random wallpaper API for free
Day09 how to create packages import package naming conventions Alibaba Development Manual
The mutual realization of C L stack and queue in I
Using C language to realize IIC driver in STM32 development
Detailed explanation of miracast Technology (I): Wi Fi display
CADD course learning (5) -- Construction of chemosynthesis structure with known target (ChemDraw)
Idea common settings
Idea to view the source code of jar package and some shortcut keys (necessary for reading the source code)
C language uses arrays to realize the intersection, union, difference and complement of sets
mysql 盲注常见函数
editplus
Differences between pycharm and idle and process -- join() in vs Code
PIL's image tool image reduction and splicing.
使用go语言读取txt文件写入excel中
Openxlsx field reading problem
Mouse click fireworks explosion effect
Day07 type of mathematical operator automatic conversion relational operator bitwise operator blind date math
Good websites need to be read carefully
Use of orbbec Astra depth camera of OBI Zhongguang in ROS melody