首页 > 代码库 > 【解题报告】[动态规划]RQNOJ - PID82 / 又上锁妖塔
【解题报告】[动态规划]RQNOJ - PID82 / 又上锁妖塔
原题地址:http://www.rqnoj.cn/problem/82
解题思路:
简单的动态规划
状态表示:DP[i][0]表示当前在第i层,且当前跳跃状态不可用,此时消耗的最短时间。
DP[i][1]表示当前在第i层,且当前跳跃状态可用,此时消耗的最短时间。
状态转移方程:
DP[i][0]=min(DP[i-1][1],DP[i-2][1]);
DP[i][1]=min(DP[i-1][0],DP[i-1][1])+t[i-1];
初始状态:
DP[0][0]=INF
DP[0][1]=0
解题代码:
1 #include<stdio.h> 2 #include<iostream> 3 using namespace std; 4 int t[10005],n; 5 int dp[10005][2]; 6 int min(int x,int y) 7 { 8 return x<y?x:y; 9 } 10 int main() 11 { 12 int i; 13 cin>>n; 14 for(i=0;i<n;i++) 15 { 16 scanf("%d",&t[i]); 17 } 18 dp[0][1]=0; 19 dp[1][0]=0; 20 dp[1][1]=t[0]; 21 for(i=2;i<=n;i++) 22 { 23 dp[i][0]=min(dp[i-1][1],dp[i-2][1]); 24 dp[i][1]=min(dp[i-1][0],dp[i-1][1])+t[i-1]; 25 //printf("%d %d\n",dp[i][0],dp[i][1]); 26 } 27 printf("%d\n",min(dp[n][0],dp[n][1])); 28 return 0; 29 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。