題干：

問題描述

　　小明喜歡在一個圍棋網站上找別人在線對弈。這個網站上所有注冊用戶都有一個積分，代表他的圍棋水平。

　　小明發現網站的自動對局系統在匹配對手時，只會將積分差恰好是K的兩名用戶匹配在一起。如果兩人分差小于或大于K，系統都不會將他們匹配。

　　現在小明知道這個網站總共有N名用戶，以及他們的積分分別是A1, A2, ... AN。

　　小明想了解最多可能有多少名用戶同時在線尋找對手，但是系統卻一場對局都匹配不起來(任意兩名用戶積分差不等于K)？

輸入格式

　　第一行包含兩個個整數N和K。
　　第二行包含N個整數A1, A2, ... AN。


　　對于30%的數據，1 <= N <= 10
　　對于100%的數據，1 <= N <= 100000, 0 <= Ai <= 100000, 0 <= K <= 100000

輸出格式

　　一個整數，代表答案。

樣例輸入

10 0
1 4 2 8 5 7 1 4 2 8

樣例輸出

6

解題報告：

? 首先，注意到我們可以把整個區間分成k份（代表模k下的不同值），這樣每一份之間互不影響。我們分開求解。

? 其實最先想到的是建k棵樹，然后就是上下級間不能全選的樹形dp的問題了，對于每個節點，權值就是該數出現的個數，但是注意到這題每個節點只會有一個孩子（除了最后一個元素）和一個父親（除了第一個元素），所以其實是組成了一條鏈，這就好做多了，沒出現過就代表權值為0唄，反正就，不影響算法的設計。

注意k==0的時候要特判一下就行了。

AC代碼：
?

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; int bk[MAX],maxx; int a[MAX]; int dp[MAX][2]; int n,k; int deal(int bei) {vector<int> vv;vv.pb(0);int res = 0;for(int i = bei; i<=maxx; i+=k) {vv.pb(bk[i]);}int up = vv.size() - 1;for(int i = 1; i<=up; i++) {dp[i][0] = max(dp[i-1][0],dp[i-1][1]);dp[i][1] = dp[i-1][0] + vv[i];}return max(dp[up][0],dp[up][1]); } int main() {cin>>n>>k;for(int i = 1; i<=n; i++) {scanf("%d",a+i);maxx = max(maxx,a[i]);bk[a[i]]++;}sort(a+1,a+n+1);if(k == 0) {printf("%d\n",unique(a+1,a+n+1) - a - 1);return 0 ;}ll ans = 0;for(int i = 0; i<k; i++) {ans += 1LL * deal(i);}printf("%lld\n",ans);return 0 ; } /* 5 3 1 4 7 2 4 */

?

總結

以上是生活随笔為你收集整理的【蓝桥杯官网训练 - 历届试题】对局匹配（dp，思维，取模）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。