ACdream 1079 Walking in the Rain (线性dp)

比眉伴天荒 2022-06-11 00:45 255阅读 0赞

题目链接:
ACdream 1079

题意:
有 n 个地板 ,你可以 从 i 跳到i+1 也可以 跳到i+2 ,我们的任务是 从 i 跳到 n 下雨了 ,第i 个地板能够坚持的天数 为a[i] 。问你最多多少天以后我们还可以跳到 第n 个地板。

题解:
dp 。
跳到 n 点的有 n−1 点和 n−2 点 。

设用 dp[i] 表示能够跳到第i 个点的最长天数。

所以转移方程为:
dp[i]=min(a[i],max(dp[i−1],dp[i−2]));

最后的答案就是:dp[n−1] 。

AC代码:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int ans,n;
  4. int dp[1234];
  5. int a[1234];
  6. int main()
  7. {
  8. cin>>n;
  9. for (int i=0;i<n;i++)
  10. {
  11. cin>>a[i];
  12. dp[i] = a[i];
  13. }
  14. dp[1]=min(a[0],a[1]);
  15. for (int i=2;i<n;i++)
  16. {
  17. dp[i]=min(a[i],max(dp[i-1],dp[i-2]));
  18. }
  19. cout<<dp[n-1]<<endl;
  20. return 0;
  21. }

发表评论

表情:
评论列表 (有 0 条评论,255人围观)

还没有评论,来说两句吧...

相关阅读