入门dp(持续更)

入门dp(持续更)
强烈推介IDEA2021.1.3破解激活,IntelliJ IDEA 注册码,2021.1.3IDEA 激活码  

大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说入门dp(持续更),希望能够帮助大家进步!!!

花了一段时间学习dp到目前为止学的还是有点浅,但一些入门的问题还是能够解决。用了一周时间打这个dp专题做完,也膜了不少大佬的题解,但好在都掌握了,抽空把这个专题给总结一下。

都是一些入门的dp,难度乱序。

问题 A: 【动态规划】探索数字迷塔

时间限制: 1 Sec  内存限制: 64 MB
提交: 74  解决: 67
[提交] [状态] [命题人:外部导入]

题目描述

晶晶最近迷上了数字迷宫游戏,整天沉浸在一串串看似简单的数字中自得其乐。数字迷宫游戏的魅力体现在变化中隐含着不变的规律,归纳是探究数字迷宫的法宝之一。图10.1-1就是一个由线连接起来的数字小方格组成的数字迷塔。
入门dp(持续更)
这个迷塔共n层,它由n×(n+1)/2个小方格组成。每个小方格中都有一个数字,并且连着下一层的两个小方格。现从塔顶走到塔底,每一步只能走到相邻的方格中,则经过方格的数字之和最大值是多少?这个问题晶晶已经琢磨一天了,她感觉异常棘手。你能帮帮她吗?

 

输入

输入数据共n+1行,第1行是一个整数n(1≤n≤1000),表示数字迷塔的高度,接下来用n行数字表示数字迷塔,其中第i行有i个正整数,且所有的正整数均不大于100。

 

输出

输出可能得到的最大和。

 

样例输入

复制样例数据

5
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16

样例输出

59
思路:状态转移方程f[i][j]表示选到(i,j)的最大值;
初始状态是f[1][1]=a[1][1];
转移方程是f[i][j]=max(f[i-1][j-1],f[i-1[j])+a[i][j];
入门dp(持续更)
入门dp(持续更)

#include <bits/stdc++.h>
 
using namespace std;
int a[1002][1002];
int f[1002][1002];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            cin>>a[i][j];
        }
    }
    f[1][1]=a[1][1];
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            f[i][j]=max(f[i-1][j-1],f[i-1][j])+a[i][j];
        }
    }
    int maxn=0;
    for(int i=1;i<=n;i++)
    {
        maxn=max(maxn,f[n][i]);
    }
    cout<<maxn<<endl;
    return 0;
}

View Code

问题 B: 【动态规划】圣诞树

时间限制: 1 Sec  内存限制: 64 MB
提交: 8  解决: 5
[提交] [状态] [命题人:admin]

题目描述

圣诞特别礼物挂在一棵圣诞树上,这棵树有n层,每层有一件礼物,每件礼物都有一个价值,有的礼物还有一些连接线,与下层的礼物相连。领取礼物的规则如下:任选一件礼物,它的下面如果有连接线,则可以继续取它连接的礼物,依此类推直至取到没有连接线的礼物才结束。你如果是第一个去取,怎样取才能获得最大的价值呢?请你编一程序解决这一问题。

 

输入

第1行只有一个数据n(n≤100),表示有n层礼物,以下有n行数据,分别表示第1~n层礼物的状态,每行至少由一个数据构成,且第一个数据表示该礼物的价值,后面的数据表示它与哪些层的礼物相连,如果每行只有一个数据则说明这层礼物没有与下层礼物相连,每个数据大小均不超过10000。

 

输出

只有一个数,表示获得的最大价值。

 

样例输入

复制样例数据

3
12 2 3
20
30

样例输出

42

这个我甚至觉得不是dp,直接能取到的都更新一遍。。
入门dp(持续更)
入门dp(持续更)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
vector<int>a[105];
int w[105];
int n,dp[105];
void read()
{
 
    cin>>n;
    getchar();
    for(int i=1;i<=n;i++)
    {
        string s;
        getline(cin,s);
        s+=' ';
        int x=0;
        int f=0;
        for(int j=0;j<s.size();j++)
        {
            if(s[j]==' ')
            {
                if(!f)
                {
                    w[i]=x;
                    x=0;
                    f=1;
                    continue;
                }
                a[i].push_back(x);
                x=0;
            }
            else
            {
                x=x*10+s[j]-'0';
            }
        }
    }
}
int main()
{
    read();
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<a[i].size();j++)
        {
            int t=a[i][j];
            dp[t]=max(dp[t],dp[i]+w[i]);
        }
        dp[i]+=w[i];
    }
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;
    return 0;
}

View Code

问题 C: 传球游戏

时间限制: 1 Sec  内存限制: 64 MB
提交: 152  解决: 87
[提交] [状态] [命题人:admin]

题目描述

上体育课时,墨老师经常带着同学们一起做游戏。这次,墨老师带着同学们一起做传球游戏,游戏规则是这样的:N个同学站成一个圆圈,其中的一个同学手里拿着一个球,当老师吹哨子时开始传球,每个同学可以把球传给自己左右的两个同学中的一个(左右任意),当老师再次吹哨子时,传球停止,此时拿着球没传出去的那个同学就是败者,要给大家表演一个节目。

聪明的张琪曼提出一个有趣的问题:有多少种不同的传球方法可以使得从张琪曼手里开始传的球,传了M次以后,又回到张琪曼手里。两种传球的方法被称作不同的方法,当且仅当这两种方法中,接到球的同学按接球顺序组成的序列是不同的。比如有3个同学1号、2号、3号,并假设张琪曼为1号,球传了3次回到张琪曼手里的方式有1à2à3à1和1à3à2à1,共两种。

 

输入

有两个用空格隔开的整数N,M(3≤N≤30,1≤M≤30)。

 

输出

有一个整数,表示符合题目的方法数。
思路:假设zqm在1号位置,初始状态 f[0][1]=1;
状态转移方程:f[i][j]=f[i-1][j-1]+f[i-1][j+1];//假设i,j都在范围内
所以最后注意一下范围就行了。
入门dp(持续更)
入门dp(持续更)

#include <bits/stdc++.h>
 
using namespace std;
int dp[35][35];
int main()
{
    int n,m;
    cin>>n>>m;
    dp[0][1]=1;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            dp[i][j]=dp[i-1][j==1?n:j-1]+dp[i-1][j==n?1:j+1];
        }
    }
    cout<<dp[m][1]<<endl;
    return 0;
}

View Code

问题 D: 【动态规划】黑熊过河

时间限制: 1 Sec  内存限制: 128 MB
提交: 74  解决: 11
[提交] [状态] [命题人:外部导入]

题目描述

晶晶的爸爸给晶晶出了一道难题:有一只黑熊想过河,但河很宽,黑熊不会游泳,只能借助河面上的石墩跳过去,它可以一次跳一墩,也可以一次跳两墩,但是每跳一次都会耗费一定的能量,黑熊最终可能因能量不够而掉入水中。所幸的是,有些石墩上放了一些食物,这些食物可以给黑熊增加一定的能量。问黑熊能否利用这些石墩安全地抵达对岸?请计算出抵达对岸后剩余能量的最大值。

 

输入

第1行包含两个整数P(黑熊的初始能量),Q(黑熊每次起跳时耗费的能量),0≤P,Q≤1000;
第2行只有一个整数n(1≤n≤106),即河中石墩的数目;
第3行有n个整数,即每个石墩上食物的能量值ai(0≤ai≤1000)。

 

输出

仅1行,若黑熊能抵达对岸,输出抵达对岸后剩余能量的最大值;若不能,则输出“NO”。

 

样例输入

复制样例数据

12 5
5
0 5 2 0 7

样例输出

6
思路:每次过河都会消耗能量,直接从石墩的初始能量上减去;
对于每个位置可以从i-1或者i-2到达,只用考虑是否能从以上位置到达即可。
入门dp(持续更)
入门dp(持续更)

#include <bits/stdc++.h>
 
using namespace std;
int dp[1000100];
int p,q;
int a[1000100];
int main()
{
    int p,q,n;
    cin>>p>>q;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i]-=q;
    }
    a[n+1]-=q;
    dp[0]=p;
    dp[1]=p-q>=0?p+a[1]:-1e9;
    for(int i=2;i<=n+1;i++)
    {
        int flag=0;
        if(dp[i-1]>=q)
        {
            dp[i]=max(dp[i],dp[i-1]+a[i]);
            flag=1;
        }
        if(dp[i-2]>=q)
        {
            dp[i]=max(dp[i],dp[i-2]+a[i]);
            flag=1;
        }
        if(!flag)
        {
            printf("NO\n");
            return 0;
        }
    }
    printf("%d\n",dp[n+1]);
    return 0;
}

View Code

问题 E: 【动态规划】抢金块

时间限制: 1 Sec  内存限制: 64 MB
提交: 71  解决: 30
[提交] [状态] [命题人:外部导入]

题目描述

地面上有一些格子,每个格子上面都有金块,但不同格子上的金块有不同的价值,你一次可以跳S至T步(2≤S<T≤10)。例如S=2,T=4,你就可以跳2步、3步或4步。你从第一个格子起跳,必须跳到最后一个格子上,请你输出最多可以获得的金块的总价值。

 

输入

第1行是格子个数n (n<1000);
第2行是S和T,保证T大于s(2≤S<T≤10);
第3行是每个格子上的金块价值Pi (Pi<10000)。

 

输出

输出最多可以获得的金块的总价值。

 

样例输入

复制样例数据

10
2 3
4 5 8 2 8 3 6 7 2 9

样例输出

36

入门dp(持续更)
入门dp(持续更)

#include <bits/stdc++.h>
 
using namespace std;
int dp[1005];
int a[1005];
int main()
{
   int n,s,t;
   cin>>n>>s>>t;
   for(int i=1;i<=n;i++)
   {
       cin>>a[i];
   }
   dp[1]=a[1];
   for(int i=2;i<=n;i++)
   {
       for(int j=s;j<=t;j++)
       {
           if(i-j<1) break;
           dp[i]=max(dp[i],dp[i-j]+a[i]);
       }
   }
   cout<<dp[n]<<endl;
    return 0;
}

View Code

问题 F: 【动态规划】维修栅栏

时间限制: 1 Sec  内存限制: 64 MB
提交: 14  解决: 8
[提交] [状态] [命题人:外部导入]

题目描述

农场的栅栏年久失修,出现了多处破损,晶晶准备维修它,栅栏是由n块木板组成的,每块木板可能已经损坏也可能没有损坏。晶晶知道,维修连续m个木板(这m个木板不一定都是损坏的)的费用是sqrt(m)。可是,怎样设计方案才能使总费用最低呢?请你也来帮帮忙。

 

输入

第1行包含一个整数n(n≤2500),表示栅栏的长度;
第2行包含n个由空格分开的整数(长整型范围内)。如果第i个数字是0,则表示第i块木板已经损坏,否则表示没有损坏。

 

输出

仅包含一个实数,表示最小维修费用;注意:答案精确到小数点后3位。

 

样例输入

复制样例数据

9
0 -1 0 1 2 3 0 -2 0

样例输出

3.000
这个题一看就是动态规划,肯定是坏了修,没坏就是dp[i]=dp[i-1];
然后枚举当前状态是从那个位置转移到来,dp[i]=min(dp[i],dp[j]+sqrt(i-j);

入门dp(持续更)
入门dp(持续更)

#include <bits/stdc++.h>
 
using namespace std;
double dp[2506];
int a[2505];
 
int main()
{
   int n;
   cin>>n;
   for(int i=1;i<=n;i++)
   {
       scanf("%d",&a[i]);
   }
   dp[0]=0;
   for(int i=1;i<=n;i++)
   {
       dp[i]=0x3f;
       if(a[i]!=0) dp[i]=dp[i-1];
       for(int j=0;j<i;j++)
       {
           dp[i]=min(dp[i],dp[j]+sqrt(i-j));
       }
   }
   printf("%.3lf\n",dp[n]);
    return 0;
}

View Code

问题 G: 【动态规划】攀登宝塔

时间限制: 1 Sec  内存限制: 64 MB
提交: 30  解决: 19
[提交] [状态] [命题人:外部导入]

题目描述

有一天,贝贝做了一个奇怪的梦,梦中他来到一处宝塔,他想要从塔的外面爬上去。这座宝塔的建造特别,塔总共有n层,但是每层的高度却不相同,这造成了贝贝爬过每层的时间也不同。贝贝会用仙术,每用一次可以让他向上跳一层或两层,这时不会耗费时间,但是每次跳跃后贝贝都将用完灵力,必须爬过至少一层才能再次跳跃。贝贝想用最短的时间爬到塔顶,可是他找不到时间最短的方案,所以请你帮他找一个时间最短的方案,让他爬到塔顶(可以超过塔高)。贝贝只关心时间,所以你只要告诉他最短时间是多少就可以了。

 

输入

第1行一个数n (n≤10000),表示塔的层数。
接下来的n行每行一个不超过100的正整数,表示从下往上每层的所需的时间。

 

输出

一个数,表示最短时间。

 

样例输入

复制样例数据

5
3
5
1
8
4

样例输出

1
可以想到的是dp的基本操作另开一维记录仙术的使用情况,0没有过,1用过;
那么dp[0][i]=min(dp[0][i-1],dp[1][i-1])+a[i];
dp[1][i]=min(dp[0][i-1],dp[0][i-2]);
入门dp(持续更)
入门dp(持续更)

#include <bits/stdc++.h>
 
using namespace std;
int a[10005];
int dp[2][10005];
int main()
{
   int n;
   cin>>n;
   for(int i=1;i<=n;i++)
   {
       cin>>a[i];
   }
   dp[0][1]=a[1];
   for(int i=2;i<=n;i++)
   {
       dp[0][i]=min(dp[0][i-1],dp[1][i-1])+a[i];
       dp[1][i]=min(dp[0][i-1],dp[0][i-2]);
   }
   cout<<min(dp[1][n],dp[0][n])<<endl;
    return 0;
}
 

View Code

 

 

转载于:https://www.cnblogs.com/Suiyue-Li/p/10982156.html

本文来源weixin_30595035,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/29770

发表评论