花了一段时间学习dp到目前为止学的还是有点浅，但一些入门的问题还是能够解决。用了一周时间打这个dp专题做完，也膜了不少大佬的题解，但好在都掌握了，抽空把这个专题给总结一下。
都是一些入门的dp，难度乱序。
问题 A: 【动态规划】探索数字迷塔
时间限制: 1 Sec 内存限制: 64 MB提交: 74 解决: 67
[提交] [状态] [命题人:外部导入]
题目描述
晶晶最近迷上了数字迷宫游戏，整天沉浸在一串串看似简单的数字中自得其乐。数字迷宫游戏的魅力体现在变化中隐含着不变的规律，归纳是探究数字迷宫的法宝之一。图10.1-1就是一个由线连接起来的数字小方格组成的数字迷塔。
这个迷塔共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];
#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; }
问题 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，直接能取到的都更新一遍。。
#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;
}
问题 C: 传球游戏
时间限制: 1 Sec 内存限制: 64 MB提交: 152 解决: 87
[提交] [状态] [命题人:admin]
题目描述
聪明的张琪曼提出一个有趣的问题：有多少种不同的传球方法可以使得从张琪曼手里开始传的球，传了Ｍ次以后，又回到张琪曼手里。两种传球的方法被称作不同的方法，当且仅当这两种方法中，接到球的同学按接球顺序组成的序列是不同的。比如有3个同学1号、2号、3号，并假设张琪曼为1号，球传了3次回到张琪曼手里的方式有1à2à3à1和1à3à2à1，共两种。
输入
输出
#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; }
问题 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到达，只用考虑是否能从以上位置到达即可。
#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 "); return 0; } } printf("%d ",dp[n+1]); return 0; }
问题 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
#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;
}
问题 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);
#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 ",dp[n]); return 0; }
问题 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]);
#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; }