公式
C - Choose Elements 解説 by en_translator
The problem can be solved with DP (Dynamic Programming).
Definition of DP
We define \(dp\) and \(ep\) by
\(dp[i] :=\) considering \((X_1,X_2,\ldots,X_i)\), can we let \(X_i = A_i\)?
\(ep[i] :=\) considering \((X_1,X_2,\ldots,X_i)\), can we let \(X_i = B_i\)?
Initial values of DP
\(dp[1]\) means “considering \((X_1)\), can we let \(X_1=A_1\)?”, which is True.
\(ep[1]\) is True in the same way.
Transitions of DP
We will determine \(dp[i]\) for \(i\geq 2\).
- If \(dp[i-1]=True\) and \(|A_{i-1}- A_i| \leq K\), then \(dp[i]=True\);
- If \(ep[i-1]=True\) and \(|B_{i-1}- A_i| \leq K\) then \(dp[i]=True\);
- Otherwise \(dp[i]=False\)
\(ep[i]\) can be found in the same way.
Answer for DP
If \(dp[N]=True\) or \(ep[N]=True\), then the answer is Yes
; otherwise, the answer is No
.
Therefore, the problem has been solved. The time complexity is \(O(N)\).
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
signed main(){
ll n,k;cin>>n>>k;
vector<ll>a(n+1),b(n+1);
for(ll i=1;i<=n;i++)cin>>a[i];
for(ll i=1;i<=n;i++)cin>>b[i];
vector<ll>dp(n+1,false),ep(n+1,false);
//Initial value
dp[1]=ep[1]=true;
//Transitions
for(ll i=2;i<=n;i++){
if(dp[i-1]){
if(abs(a[i-1]-a[i])<=k)dp[i]=true;
if(abs(a[i-1]-b[i])<=k)ep[i]=true;
}
if(ep[i-1]){
if(abs(b[i-1]-a[i])<=k)dp[i]=true;
if(abs(b[i-1]-b[i])<=k)ep[i]=true;
}
}
//Answer
if(dp[n]||ep[n])cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
投稿日時:
最終更新: