ACdream 1079 Walking in the Rain (线性dp)
题目链接:
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代码:
#include<bits/stdc++.h>
using namespace std;
int ans,n;
int dp[1234];
int a[1234];
int main()
{
cin>>n;
for (int i=0;i<n;i++)
{
cin>>a[i];
dp[i] = a[i];
}
dp[1]=min(a[0],a[1]);
for (int i=2;i<n;i++)
{
dp[i]=min(a[i],max(dp[i-1],dp[i-2]));
}
cout<<dp[n-1]<<endl;
return 0;
}
还没有评论,来说两句吧...