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.     }
  15.     dp[1]=min(a[0],a[1]);
  16.     for (int i=2;i<n;i++) 
  17.     {
  18.         dp[i]=min(a[i],max(dp[i-1],dp[i-2]));
  19.     }
  20.     cout<<dp[n-1]<<endl;
  21.     return 0;
  22. }

发表评论

表情：
评论列表 （有 0 条评论，255人围观）

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

相关阅读