試題 歷屆試題 對(duì)局匹配

資源限制 時(shí)間限制：1.0s 內(nèi)存限制：256.0MB

---

$Daily English

孩子害怕黑暗，情有可原；人生真正的悲劇，是成人害怕光明。
We can easily forgive a child who is afraid of the dark;the real tragedy of life is when men are afraid of light.

問題描述

小明喜歡在一個(gè)圍棋網(wǎng)站上找別人在線對(duì)弈。這個(gè)網(wǎng)站上所有注冊(cè)用戶都有一個(gè)積分，代表他的圍棋水平。

小明發(fā)現(xiàn)網(wǎng)站的自動(dòng)對(duì)局系統(tǒng)在匹配對(duì)手時(shí)，只會(huì)將積分差恰好是K的兩名用戶匹配在一起。如果兩人分差小于或大于K，系統(tǒng)都不會(huì)將他們匹配。

現(xiàn)在小明知道這個(gè)網(wǎng)站總共有N名用戶，以及他們的積分分別是A1, A2, … AN。

小明想了解最多可能有多少名用戶同時(shí)在線尋找對(duì)手，但是系統(tǒng)卻一場(chǎng)對(duì)局都匹配不起來(任意兩名用戶積分差不等于K)？
輸入格式
　　第一行包含兩個(gè)個(gè)整數(shù)N和K。
　　第二行包含N個(gè)整數(shù)A1, A2, … AN。

對(duì)于30%的數(shù)據(jù)，1 <= N <= 10
　　對(duì)于100%的數(shù)據(jù)，1 <= N <= 100000, 0 <= Ai <= 100000, 0 <= K <= 100000

輸出格式

一個(gè)整數(shù)，代表答案。

樣例輸入

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

樣例輸出

6

思路：

表面上看起來像二分圖匹配，但是問的不是！！
樣例給的也只是特殊的一種情況。

• 特殊情況：k = 0:
  那么相同的數(shù)分為一組，每組中取一個(gè)就是ans。
• 一般的情況：k > 0:
  比如： n = 8,k = 1:
  1 2 3 4 5 7 8 9
  那么根據(jù)k可以將上述數(shù)分為兩組：
  {1，2，3，4，5}為一組；
  {7，8，9}為一組。
  在這里的一組中選不選一個(gè)數(shù)，很明顯需要看這個(gè)數(shù)出現(xiàn)的次數(shù)。
  即數(shù)出現(xiàn)的次數(shù)作為選這個(gè)數(shù)的價(jià)值。
  比如有：n = 8,k = 1;
  1 2 3 4 5 2 4 4
  可以分為一組：{1，2，3，4，5}
  對(duì)應(yīng)的價(jià)值為：{1，2，1，3，1}
  在一組中，每個(gè)數(shù)只有選與不選兩種決策，而且任意兩個(gè)相鄰的數(shù)不能同時(shí)選：
  假設(shè)dp[i]為一組中以第i個(gè)數(shù)結(jié)尾能夠獲得的最大價(jià)值。
  那么很容易得出狀態(tài)轉(zhuǎn)移方程：
  dp[i] = max(dp[i-2] + v[i],dp[i-1]);
  對(duì)于可以分成多個(gè)組的一個(gè)序列，那么每組按一組的方式dp，累加每組能夠獲得的最大價(jià)值即為ans。

代碼：

/* v[i]:選擇數(shù)i的價(jià)值 vis[i]:標(biāo)記數(shù)i是否已經(jīng)被分組 group[]:存每組的元素 dp[i]:。。。 */ #include <iostream> #include <cstdio> using namespace std; const int N = 1e5+5; int v[N]; bool vis[N]; int dp[N]; int group[N]; int main() {int n,k;scanf("%d%d",&n,&k);int x;int minx = 1e9,maxx = -1;for(int i = 1; i <= n; i++){scanf("%d",&x);v[x]++;minx = min(minx,x);maxx = max(maxx,x);}int ans = 0;if(k == 0){for(int i = minx; i <= maxx; i++){if(v[i]) ans++;}}else{for(int i = minx; i <= maxx; i++){if(!v[i] || vis[i]) continue;int t = 0;for(int j = i; j <= maxx; j+= k){vis[j] = true;group[++t] = j;dp[t] = 0;}dp[1] = v[group[1]];for(int j = 2; j <= t; j++){dp[j] = max(dp[j-2]+v[group[j]],dp[j-1]);}ans += dp[t];}}printf("%d\n",ans);return 0; } 與50位技術(shù)專家面對(duì)面20年技術(shù)見證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的#每日一题 对局匹配（dp）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。