哇真难啊,没注意到 可以开 dp[N][3][3]这种性质,也就是三个相同的顺子可以变成三个刻子,所以我们维护顺子的数目就不用超过三了,又因为每张牌i,只会被i-1,i-2,影响,所以额外开两维记录(记录的信息在下面)就够了。
开始也想到了对子和顺子那题,,但是那题记得学长讲的是堆栈做法,,,这个一看就是dp,就感觉很卜。
哇雀魂白玩了!雀魂!卸载!
看的官方题解,还是挺好懂的。
意思就是 用 f[i][t1][t2] 表示到考虑到i这个位置, t1表示[i-1,i,i+1]的数量,t2表示[i,i+1,i+2]的数量,t3表示[i+1.i+2,i+3]的数量。
然后我们就可以 dp[i+1][t2][t3]=max(dp[i][t1][t2]+t3+ (num[i+1]-need)/3 );这样维护下去。
还有别的dp方法,我不会。
我老人家昨晚又表演了两个小时小品。。。感觉很搞笑哇。九点半起床读了读题。。
为什么大家都会E啊,我觉得好难啊。。。
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N=1e6+5; 4 int n,m,a,num[N]; 5 int f[N][3][3]; 6 bool check(int i,int t1,int t2,int t3){ 7 return num[i+3]>=t3&&num[i+2]>=t2+t3&&num[i+1]>=t1+t2+t3&&num[i]>=t1+t2&&num[i-1]>=t1; 8 } 9 int main(){ 10 ios::sync_with_stdio(false); 11 cin>>n>>m; 12 for(int i=1;i<=n;i++){ 13 cin>>a; 14 num[a]++; 15 } 16 int ans=0; 17 for(int i=0;i<=m;i++) { 18 for(int t1=0;t1<3;t1++){ 19 for(int t2=0;t2<3;t2++){ 20 for(int t3=0;t3<3;t3++){ 21 if(check(i,t1,t2,t3)) 22 f[i+1][t2][t3]=max(f[i+1][t2][t3],f[i][t1][t2]+t3+(num[i+1]-t1-t2-t3)/3); 23 } 24 } 25 } 26 } 27 cout<<f[m+1][0][0]<<endl; 28 }View Code