表示,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]); }