表示,dp的魅力;
只要知道这题用dp做,就差不多了;怎么想到dp?一方面做题多,另一方面排除法,别的都不行。
这道题求最小值,最值一般dp。二分,贪心。
最后选dp;
dp[][0/1]表示,到达i的时候,前i-1个数满足题意,第i个数是否需要+/-1;
需要判断a[i]与a[i-1]的关系;
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=300000;
ll a[maxn],b[maxn],dp[maxn][2];
int main()
{
ll n,ans=0,ok=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i]>>b[i];
}
for(ll i=1;i<=n;i++)
{
if(a[i]==a[i-1])
{
dp[i][0]=dp[i-1][1];
dp[i][1]=dp[i-1][0]+b[i];
}
else if(a[i-1]+1==a[i])
{
dp[i][0]=dp[i-1][0];
dp[i][1]=min(dp[i-1][0],dp[i-1][1])+b[i];
}
else if(a[i-1]==a[i]+1)
{
dp[i][0]=min(dp[i-1][1],dp[i-1][0]);
dp[i][1]=dp[i-1][1]+b[i];
}
else {
dp[i][0]=min(dp[i-1][1],dp[i-1][0]);
dp[i][1]=min(dp[i-1][1],dp[i-1][0])+b[i];
}
}
cout<<min(dp[n][1],dp[n][0]);
}
京公网安备 11010502036488号