题目传送门:C - Choose Elements (atcoder.jp)
题目大意
给定长度为N的整数序列 A 和 B ,能否构造出一个序列X,使得Xi = Ai or Bi,且| Xi - X(i-1) | <= K。
思路
这里用dp的思路,dp[i][0]表示能够从起点构造到第i位,并使Xi = Ai,dp[i][1]则表示Xi = Bi。
状态转移方程就是转移一下“到起点的连通性”。
对于第i列,只要i - 1列中任意一个能够连通到Ai(即差的绝对值小于等于K)那么dp[i][0]就等于1,否则为0。
代码
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 2e5 + 10; int A[maxn], B[maxn]; int dp[maxn][2]; int getabs(int x){return x < 0 ? -x : x;} signed main() { int N, K;cin >> N >> K; for(int i = 1;i <= N; ++ i)scanf("%lld",A + i); for(int i = 1;i <= N; ++ i)scanf("%lld",B + i); dp[1][1] = dp[1][0] = 1; for(int i = 2;i <= N; ++ i) { if((dp[i - 1][0] && getabs(A[i] - A[i - 1]) <= K) || (getabs(A[i] - B[i - 1]) <= K && dp[i - 1][1]))dp[i][0] = 1; if((dp[i - 1][0] && getabs(B[i] - A[i - 1]) <= K) || (getabs(B[i] - B[i - 1]) <= K && dp[i - 1][1]))dp[i][1] = 1; } if(dp[N][1] || dp[N][0])printf("Yes\n"); else printf("No\n"); return 0; }
Comments NOTHING