dp小题 2018-1-30

本文主要是介绍dp小题 2018-1-30，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

动态规划的两个要素：最优子结构和子问题重叠

题意：

天天酷跑，给一个2*n的格子，初始时在（2，1）这个点上，每次两种操作

从（2，i）移动到（2，i+1）

从（2，i）跳起，经过（1，i+1）（1，i+2）跳到（2，i+3）

当到达（1，n）或者（2，n）的时候，游戏结束，每个格子上有一个分数，游戏总分数就是经过的格子分数之和，求能获得的分数的最大值

Sample：

0 0 1 1 0

2 1 2 0 1

答案6

思路：

DP[i]表示，到第i个格子而且在地面时能获得的最高分数，答案就是DP[n]

状态转移：

1.从i-1个格子直接走过来dp[i]← dp[i-1] + score[2][i]

2.从i-3个格子跳过来dp[i]← dp[i-3] + score[1][i-2] + score[1][i-1] + score[2][i]

‘

递归实现：

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <algorithm>  
using namespace std;  int a[2][100005];  
int d[100005];  
int vis[100005];  
int dp(int i)  
{  if(vis[i]) return d[i];  d[i] = a[1][i];  if(i == 0)  return a[1][0];  if(i <= 2)  d[i] += dp(i-1);  else  {  d[i] += max(dp(i-1) , dp(i-3) + a[0][i-1] + a[0][i-2]);  }  vis[i] = 1;  return d[i];  
}  int main()  
{  int T, n;  scanf("%d", &T);  while(T--)  {  memset(a, 0, sizeof(a));  scanf("%d", &n);  for(int i=0; i<n; i++)  scanf("%d", &a[0][i]);  for(int i=0; i<n; i++)  scanf("%d", &a[1][i]);  memset(d, 0, sizeof(d));  memset(vis, 0, sizeof(vis));  int t;  if(n==3)  {  t = max(a[0][2]+a[0][1]+a[1][0], a[1][2]+a[1][1]+a[1][0]);  }  else if(n==2)  {  t = max(a[0][1]+a[1][0], a[1][1]+a[1][0]);  }  else if(n == 1)  {  t = a[1][0];  }  else if(n >3)  {  t = max(dp(n-1), dp(n-3) + a[0][n-1] + a[0][n-2]);  t = max(t, dp(n-2) + a[0][n-1]);  }  printf("%d\n", t);  }  return 0;  
}  

递推实现：

#include <iostream>  
#include <cstring>  
#include <cstdio>  
#include <algorithm>  
using namespace std;  #define N 200005  int dp[N], a[2][N];  int main() {  int n, t;  cin >> t;  while (t--) {  cin >> n;  memset(a, 0, sizeof(a));  for (int j = 0; j < 2; j++) for (int i = 1; i <= n; i++) scanf("%d", &a[j][i]);  dp[0] = 0;  for (int i = 1; i <= n + 2; i++) {  dp[i] = dp[i - 1] + a[1][i];  if (i > 3) dp[i] = max(dp[i], dp[i - 3] + a[0][i - 2] + a[0][i - 1] + a[1][i]);  }  printf("%d\n", dp[n + 2]);  }  return 0;  
}  

这篇关于dp小题 2018-1-30的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---