dp专题（一）
ABC346:E - Maximum Glutton
问题陈述
高桥为斯努克准备了 NN 道菜。这些菜肴的编号从 11 到 NN ，菜肴 ii 的甜度为 AiAi ，咸度为 BiBi 。高桥可以按照自己喜欢的顺序排列这些菜肴。斯助会按照排列顺序吃掉这些菜肴，但如果他吃过的菜肴的总甜度超过 XX 或总咸度超过 YY ，他就不会再吃任何菜肴。高桥希望斯助吃尽可能多的菜肴。求如果高桥把菜肴摆放得最合理，斯助最多吃多少道菜？
限制因素
- 1≤N≤801≤N≤80
- 1≤Ai,Bi≤100001≤Ai,Bi≤10000
- 1≤X,Y≤100001≤X,Y≤10000
- 所有输入值均为整数。
输出
将答案打印为整数。
做法
一般情况dp数组下标为：考虑了前i道菜，累计甜度是j，累计咸度是k。dp值：选了几道菜。但数组开不下，因此可以换一下键和值位置。
#include<bits/stdc++.h>
using namespace std;
int n,x,y;
struct ty{
int a,b;
};
int dp[100][100][10010];//下标：考虑了前i道菜，选了j道菜，累计咸度是k。dp值：甜度
int main(){
cin>>n;
scanf("%d%d",&x,&y);
vector<ty> v(n+1);
v[0].a=0,v[0].b=0;
for(int i=1;i<=n;i++){
scanf("%d%d",&v[i].a,&v[i].b);
}
memset(dp,0x3f,sizeof(dp));
dp[0][0][0]=0;
for(int i=1;i<=n;i++) {
for(int j=0;j<=i;j++){
for(int k=0;k<=y;k++){
dp[i][j][k]=dp[i-1][j][k];//当前不选
if(j>0&&k>=v[i].b) dp[i][j][k]=min(dp[i-1][j-1][k-v[i].b]+v[i].a,dp[i][j][k]);
}
}
}
int cnt=0,sign=0;
for(int i=n;i>=0;i--){//选了i道菜
for(int j=y;j>=0;j--){//累积咸度
if(dp[n][i][j]<=x){
cnt=i;
sign=1;
break;
}
}
if(sign) break;
}
cout<<min(cnt+1,n);
}2024睿抗省赛：RC-u5.工作安排
题目
小 K 有 N 项工作等待完成，第 i 项工作需要花 ti 单位时间，必须在 di 时刻或之前完成，报酬为 pi。假设小 K 工作时刻从 0 开始，且同一时刻只能做一项工作、工作一旦开始则不可中断或切换至其他工作，请你帮小 K 规划一下如何选择合适的工作，使小 K 可以获得最多的报酬。
输入格式:
输入第一行是一个正整数 T (≤5)，表示数据的组数。
接下来有 T 组数据，每组数据第一行是一个正整数 N (≤5000)，表示待完成工作的数量。接下来的 N 行，每行三个非负整数 ti、di、pi (均 ≤5000；1≤i≤N)，表示第 i 项工作需要花费的时间、截止时间以及报酬。
输出格式:
对于每组数据，输出小 K 能获得最多的报酬是多少。
做法
dp数组 下标：考虑前i项工作，当前时间为j。dp值：报酬
滚动数组：开不下那么大的数组，便用滚动数组。跟直接省去一维相比，同样能达到降维，但好写很多。
#include<bits/stdc++.h>
using namespace std;
int dp[10010];
int g[10010];
int n,t;
struct ty{
int t,d,p;
};
bool cmp(ty a,ty b){
return a.d<b.d;
}
int main(){
cin>>t;
while(t--){
memset(dp,0,sizeof(dp));
memset(g,0,sizeof(g));
cin>>n;
vector<ty> v(n+1);
for(int i=1;i<=n;i++) scanf("%d%d%d",&v[i].t,&v[i].d,&v[i].p);
sort(v.begin(),v.end(),cmp);//因为截止时间有影响，所以要排个序，截至时间早的先考虑
for(int i=1;i<=n;i++){
//本来是这么写的，但是开不了那么大的数组，所以我们就考虑滚动数组
// for(int j=0;j<=v[i].d;j++){
// dp[i][j]=dp[i-1][j];//不干
// if(j-v[i].t>=0) dp[i][j]=max(dp[i][j],dp[i-1][j-v[i].t]+v[i].p);
// }
for(int j=0;j<=5000;j++) dp[j]=0;
for(int j=0;j<=v[i].d;j++){
dp[j]=g[j];//第i个任务不干
if(j-v[i].t>=0) dp[j]=max(dp[j],g[j-v[i].t]+v[i].p);
}
for(int j=0;j<=5000;j++) swap(g[j],dp[j]);
}
int ans=0;
for(int i=0;i<=5000;i++) ans=max(ans,g[i]);
cout<<ans<<endl;
}
}牛客周赛53：D小红组比赛
题目描述
\,\,\,\,\,\,\,\,\,\,小红希望出一场题目，但是他的实力又不够，所以他想到可以从以前的比赛中各抽一题，来组成一场比赛。不过一场比赛的难度应该是有限制的，所以所以这一场比赛会给一个目标难度分数 target\rm targettarget 。
\,\,\,\,\,\,\,\,\,\,小红选 nnn 场比赛，每场 mmm 个题，小红会从每一场选一道题，使其组成的题的难度分数尽量接近 target\rm targettarget 。小红想知道挑选的题的难度分数与 target\rm targettarget 相差的最小值是多少。
输入描述:
\,\,\,\,\,\,\,\,\,\,第一行输入两个整数 n,m (1≤n≤100,1≤m≤20)n, m\ (1 \leq n \leq 100, 1 \leq m \leq 20)n,m (1≤n≤100,1≤m≤20) 代表小红选了 nnn 场比赛，每场比赛有 mmm 道题。
\,\,\,\,\,\,\,\,\,\,此后 nnn 行，第 iii 行输入 mmm 个整数 ai,j (1≤ai,j≤50)a_{i,j}\ (1 \leq a_{i,j} \leq 50)ai,j (1≤ai,j≤50) 代表第 iii 场比赛的第 jjj 道题的难度分数。
\,\,\,\,\,\,\,\,\,\,最后一行输入一个整数 target (1≤target≤5000){\rm target}\ (1 \leq {\rm target} \leq 5000)target (1≤target≤5000) 代表小红希望这一场比赛的难度分数。
输出描述:
\,\,\,\,\,\,\,\,\,\,在一行上输出一个整数，表示挑选的题的难度分数与 target\rm targettarget 相差的最小值。
示例1
输入
3 3 1 4 7 2 5 8 3 6 9 10
输出
1
说明
\,\,\,\,\,\,\,\,\,\,小红可以选第一场比赛的第一道题，第二场比赛的第一道题，第三场比赛的第二道题，这样挑选的题的难度分数为 1+2+6=91 + 2 + 6 = 91+2+6=9，与 target\rm targettarget 相差的最小值为 111。
做法
dp数组 下标：考虑前i个，当前分数为j。值：有没有这个分数
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[160][60],dp[110][5010];
int t;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
cin>>t;
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
for(int k=0;k<=5000;k++){
if(dp[i][k]) continue;//防止有的又被设成没有了
if(k>=a[i][j]) dp[i][k]=dp[i-1][k-a[i][j]];
}
}
}
int minn=0x3f3f3f;
for(int i=0;i<=5000;i++){
if(dp[n][i]){
minn=min(minn,abs(t-i));
}
}
cout<<minn;
}原文地址：https://blog.csdn.net/2301_80718054/article/details/140856242
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！