动态规划类题型

编程入门行业动态更新时间:2024-10-07 17:32:58

动态规划类<a href=https://www.elefans.com/category/jswz/34/1767307.html style= 题型"/>

动态规划类题型

法兰要塞（zzulioj周赛7）

题目描述

“分享狼血，与子同胞”
“漫步深渊，心怀正义”
“侍奉光明，斩杀黑暗”
“因剑而生，因剑而死”
“深渊无尽，我等将不娶妻，不生子，只求一世荣耀”
“光阴有时，我等必守此誓，献此生，但愿诸界太平”
无火的余烬，你追随者古老的誓言来到了法兰要塞，为了通过烽火试炼，你必须收集足够多的灵魂。
已知要塞里有n个怪物，不同的怪物有着不同的血量a。每次，你可以选择消灭一只怪物，同时所有血量为a+1和a-1的怪物也会死去。同时你可以获得a个灵魂。

输入

第一行输入一个整数n（1<=n<=10^5）
第二行输入n个整数a1,a2,…an（1<=ai<=10^5）

输出

请输出无火的余烬可以获得的最大灵魂数量

样例输入

9
1 2 1 3 2 2 2 2 3

样例输出

分析

对于n个血量的怪物，可以从小到大对其进行动态规划思想。从1开始（因为从单侧开始只需要考虑i+1即可），dp[1][0]为不杀该怪物的灵魂，dp[1][1]为杀该怪物的灵魂。随后分析i+1的dp，即2的dp。由于怪物最大血量为10^5 ，则dp[10^5]即为最终求值

标程

#include<bits/stdc++.h>
using namespace std;
long long soul[100005],s[100005],dp[100005][2];
int main()
{int n,a;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a);soul[a]+=a;  //soul是指a血的怪物全部杀掉可以获得的灵魂}for(int i=1;i<=100005;i++)   //此处i指怪物血量 {dp[i][0]=max(dp[i-1][1],dp[i-1][0]);dp[i][1]=dp[i-1][0]+soul[i];}long long ans=max(dp[100005][1],dp[100005][0]);printf("%lld",ans);
}

学长的棒棒糖（zzulioj周赛7）

题目描述

学长有n个棒棒糖，他每次最多可以吃k个，请问他有多少种方法来吃棒棒糖

输入

输入两个整数n， k（1 <= n <= 100000) （1 <= k <= 100）

输出

一个正整数，为不同方法数，由于答案可能很大，你需要输出对答案mod100003的结果。

样例输入

5 2

样例输出

提示

8种例子如下：
1-1-1-1-1
2-1-1-1
1-2-1-1
1-1-2-1
1-1-1-2
2-2-1
2-1-2
1-2-2

分析

不太明白为什么要用到dp，目前仅仅只能通过找规律发现规律满足n前k项dp相加之和，如n=5，k=3
dp[5]=dp[4]+dp[3]+dp[2]

标程

#include<bits/stdc++.h>
using namespace std;
int main()
{int n,k,dp[100005];memset(dp,0,sizeof(dp));scanf("%d%d",&n,&k);dp[0]=1;dp[1]=1;for(int i=2;i<=n;i++){for(int j=1;j<=k;j++){if(i-j<0)break;dp[i]+=dp[i-j];dp[i]=dp[i]%100003;}}printf("%d",dp[n]);}

hdu 1087 Super Jumping! Jumping! Jumping!

现在，有一种象棋游戏叫“超级跳跃！跳跃的！跳跃的！“在HDU非常流行也许你是个好孩子，对这项运动知之甚少，所以我现在就给你介绍一下。
这个游戏可以由两个或两个以上的玩家玩。它由一个棋盘（棋盘）和一些棋子（棋子）组成，所有棋子都用正整数或“开始”或“结束”标记。玩家从起点开始，最后必须跳入终点。在跳跃的过程中，玩家将访问路径中的棋子，但是每个人都必须从一个棋子跳到另一个棋子绝对大（你可以假定起点是最小的，终点是最大的）。所有玩家都不能倒退。一跳可以从一个棋子跳到另一个棋子，也可以跨越许多棋子，甚至你可以直接从起点跳到终点。在这种情况下你当然得零分一个运动员是胜利者，只要他能根据他的跳跃解决方案得到更大的分数。注意，你的分数来自于你跳跃路径中棋子的价值之和。
你的任务是根据给定的棋子列表输出最大值。

Input

输入包含多个测试用例。每个测试用例在一行中描述如下：
N value_1 value_2 …value_N
保证N不大于1000，且所有值均在int范围内。
以0开头的测试用例终止输入，不处理此测试用例。

Output

对于每种情况，按规则打印最大值，一行打印一次。

Sample Input

3 1 3 2
4 1 2 3 4
4 3 3 2 1
0

Sample Output

4
10
3

分析

和法兰要塞思路不同，并没有分开讨论1和0两种情况，思维方式有待提高

#include<iostream>
#include<algorithm>
using namespace std;
int a[1005],dp[1005];
int main()
{int n;while(scanf("%d",&n)!=EOF && n){for(int i=1;i<=n;i++){scanf("%d",&a[i]);dp[i]=a[i];}for(int i=1;i<=n;i++){for(int j=1;j<i;j++){if(a[i]>a[j])dp[i]=max(dp[i],dp[j]+a[i]);}}int ans=0;for(int i=1;i<=n;i++)ans=max(ans,dp[i]);printf("%d\n",ans);}
}