自学内容网 自学内容网

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)!