問題描述
　　小明喜歡在一個圍棋網站上找別人在線對弈。這個網站上所有注冊用戶都有一個積分，代表他的圍棋水平。
　　小明發現網站的自動對局系統在匹配對手時，只會將積分差恰好是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
開始題意沒理解清楚，當初模擬做了，結果只過了一個案例。
然后發現是dp,就比如：a[i+k(n-1)], a[i+kn], a[i+k(n+1)] 時候，模擬是做不了的，同時這個給了我思路，我可以通過分組的動態規劃來寫，及分組公式為 i+kn.(0<=i<k, i+kn<maxx)
當k=2，maxx=10 的分組情況：
i=0: 0 2 4 6 8 10
i=1: 1 3 5 7 9
狀態轉移方程為dp[j]=max(dp[j-1],dp[j-2]+cnt[j]), dp[j-1]=a[i+k(n-1)], dp[j-2]=a[i+k(n-2)], cnt[j]=a[i+kn].

#include <iostream> #include<math.h> #include <stdio.h> using namespace std; #define max(a,b) ((a) > (b) ? (a) : (b)) #define min(a,b) ((a) < (b) ? (a) : (b)) const int maxn = 100000+10;//范圍要包含數據范圍 int a[maxn]; int dp[maxn]; int cnt[maxn]; int n,k; int main(){cin >> n >> k;int maxx = -1;int ans = 0;for (int i = 0; i < n; i++) {int b;cin >> b;maxx = max(maxx, b);//找到最大的數，這樣遍歷就不用每次遍歷到maxn;a[b]++;//cout << a[b] << endl;}if (k == 0) {//當k=0，不用分組，只要不為0 就加一for (int i = 0; i <= maxx; i++) {if(a[i]!=0)ans ++;}}else {/*分組記分為 i+kn 其中i:0 到 k-1，且i+kn<=最大的數*/for (int i = 0; i < k; i++) {//控制iint y = 0;for (int j = i; j <= maxx; j+=k) {//控制n//cout << j << endl;cnt[y++] = a[j];//把分組后的每個數值存儲在cnt里面 cnt[0]=a[i+0*k],cnt[1]=a[i+1*k]以此類推}dp[0] = cnt[0];//把dp[0]初始化cnt[0]for (int j = 1; j < y; j++) {if (j == 1) {dp[j] = max(dp[0], cnt[j]);//cout << dp[j] << endl;}else {//相鄰的兩組不能放在一起，dp[j]=max( dp[i-1],dp[i-2]+cnt[j])dp[j] = max(dp[j - 1], dp[j - 2] + cnt[j]);}}ans += dp[y - 1];}}//cout << endl;cout << ans << endl;return 0; }

總結

以上是生活随笔為你收集整理的试题 历届试题 对局匹配（动态规划）保证简单的全部內容，希望文章能夠幫你解決所遇到的問題。

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