【CF global1 D / CF1110D】 Jongmah

題意

你有n個數字，范圍[1, m]，你可以選擇其中的三個數字構成一個三元組，但是這三個數字必須是連續的或者相同的，每個數字只能用一次，問這n個數字最多構成多少個三元組?

分析

這里想談一下DP的一個套路，捆綁
有的DP題目，它可能會要求和一些東西捆綁，求方案數，這種時候如何單點設置狀態呢？
以這個題為例，只考慮前i種數字，對于數字i,它可能 (i,i,i) (i-2,i-1,i) (i-1,i) (i,) 如果是后兩種，它還未構成一個合法的序列，我們還不知道是否存在i+1來完善它
也就是考慮前i種數字的時候，后兩種不應該被計入方案數里，但轉移的時候我們要用到他們的數量，這里就可以再用兩維將他的數量捆綁起來一起轉移
狀態
dp[i][j][k] 表示只考慮前i種數字，捆綁了j個(i-1,i) k個(i)的最大方案數
初始條件
dp[0][0][0] = 0 ,others = -inf
因為假設只考慮前0種數字（實際不存在，假定數量為0),它無法構成任何三元組，但是轉移到前1種可以用前0種轉移過來
其余的都是未求解狀態 ，默認為負無窮
轉移方案
我們有a[i+1]個i+1
考慮如何從dp[i][j][k]轉移到前i+1個去
考慮第一個貪心策略：如果有未完成的三元組，優先補全它，因為如果不補全，它便會向后需求，這樣無論如何也不會讓答案更大
所以我們需要用j+k個i+1 去補全(i-1,i)和(i)這樣我們形成了j個(i-1,i,i+1)可以計入方案數里，以及k個(i,i+1)
還剩下a[i+1] - j - k個i+1
枚舉我們捆綁多少個(i+1)，將剩下的全部變成(i+1,i+1,i+1)
這樣轉移的方程就確定了
dp[i+1][k][t] = max ( dp[i+1][k][t] , dp[i][j][k] + j + (a[i+1]-j-k-t)/3)
最終答案就是只考慮前m個數字，最大的答案
考慮第二個貪心策略，如果我們夠造了三個順子，他們其實可以重組成三個同花，也就是說，j,k一定小于3

代碼

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1000005];
int dp[1000005][3][3];
int main() {ios::sync_with_stdio(false);cin.tie(0);int tmp;cin>>n>>m;for(int i=1;i<=n;i++) {cin>>tmp;a[tmp]++;}memset(dp,0x80,sizeof(dp));dp[0][0][0] = 0;for(int i=0;i<m;i++) {for(int j=0;j<3;j++) {for(int k=0;k<3;k++) {int res = a[i+1] -j - k;for(int t=0;t<3&&t<=res;t++) {dp[i+1][k][t] = max(dp[i+1][k][t],dp[i][j][k]+j+(res-t)/3);}}}}int ans =0 ;for(int i=0;i<3;i++) for(int j=0;j<3;j++) ans = max(ans,dp[m][i][j]);cout<<ans<<endl;}