brief outline of the meaning of the topic
Given a deck of cards, find the least number of times to play all the cards in the hand. (Play as it is given)
title
analyze
Because finding the minimum number of times is obviously wrong to be directly greedy, but it's impossible to write directly\(dp\) So we can only explode the search for all cases, but this will obviously time out, only pruning, we record the number of individual digits, but in fact, except for the straight, the other out of the card does not care about the size of the digits, only the number. So we deal with the jokers separately, and then record only the\(js[i]\) represent\(i\) The number of digits in a card is then simulated in the play. This time we found that as soon as\(js\) One answer is the same has nothing to do with sequential order etc., so a memorized search (dp) record will do. But be sure to note some special cases, e.g. double kings can come out as pairs, not be used as pairs, it is possible to split three's into one and two better, ditto four's into one and three or two and two.
coding
Click to view code
#include <bits/stdc++.h>
using namespace std;
int t,n,cnt[20],js[10],xz[5]={0,5,3,2};
int dp[30][30][30][30];
int dfs()
{
if(dp[js[1]][js[2]][js[3]][js[4]]!=-1)return dp[js[1]][js[2]][js[3]][js[4]];
int sum=n;
if(js[2])
{
js[2]--;js[1]+=2;
sum=min(sum,dfs());
js[2]++;js[1]-=2;
}//chai2
if(js[3])
{
js[3]--;js[1]+=1,js[2]+=1;
sum=min(sum,dfs());
js[3]++;js[1]-=1,js[2]-=1;
}
if(js[4])
{
js[4]--;js[1]+=1,js[3]+=1;
sum=min(sum,dfs());
js[4]++;js[1]-=1,js[3]-=1;
js[4]--;js[2]+=2;
sum=min(sum,dfs());
js[4]++;js[2]-=2;
}
if(js[1])js[1]--,sum=min(sum,1+dfs()),js[1]++;//danpai
if(js[2])js[2]--,sum=min(sum,1+dfs()),js[2]++;//duizi
if(js[3])js[3]--,sum=min(sum,1+dfs()),js[3]++;//san
if(js[4])js[4]--,sum=min(sum,1+dfs()),js[4]++;//bombshell
if(js[3]&&js[1])
{
js[3]--;js[1]--;
sum=min(sum,1+dfs());
js[3]++;js[1]++;
} //3+1
if(js[3]&&js[2])
{
js[3]--;js[2]--;
sum=min(sum,1+dfs());
js[3]++;js[2]++;
} //3+2
if(js[2]>=2&&js[4])
{
js[4]--;js[2]-=2;
sum=min(sum,1+dfs());
js[4]++;js[2]+=2;
}
if(js[1]>=2&&js[4])
{
js[4]--;js[1]-=2;
sum=min(sum,1+dfs());
js[4]++;js[1]+=2;
}//4+2
return dp[js[1]][js[2]][js[3]][js[4]]=min(sum,js[1]+js[2]+js[3]+js[4]);
}
int shunzi(int step)
{
int ans=n;
for(int k=1;k<=3;k++)
for(int i=1;i<=12-xz[k]+1;i++)
{
int tot=0;
for(int j=i;j<=12;j++)
{
if(cnt[j]>=k)tot++;
else break;
}
for(int j=i+xz[k]-1;j<=i+tot-1;j++)
{
// cout<<i<<" "<<j<<'\n';
for(int l=i;l<=j;l++)js[cnt[l]]--,cnt[l]-=k,js[cnt[l]]++;
ans=min(ans,shunzi(step+1));//Multiple straights are possible.
for(int l=i;l<=j;l++)js[cnt[l]]--,cnt[l]+=k,js[cnt[l]]++;
}
}
ans=min(ans,step+dfs());//Run after the jungler.
if(cnt[14]==2)
{
js[1]-=2;
ans=min(step+1+dfs(),ans);//We'll run again when it's time for the king's bomb.。
js[1]+=2;
}
return ans;
}
int main()
{
ios::sync_with_stdio(0);
(0);(0);
cin>>t>>n;
memset(dp,-1,sizeof(dp));
dp[0][0][0][0]=0;
while(t--)
{
memset(cnt,0,sizeof(cnt));
memset(js,0,sizeof(js));
for(int i=1;i<=n;i++)
{
int ai,bi;cin>>ai>>bi;
if(ai>=1)
{
if(ai>=3)cnt[ai-2]++;
else cnt[ai+11]++;//A,2
}
else cnt[14]++;//wang
}
for(int i=1;i<=14;i++)js[cnt[i]]++;
if(cnt[14]&&cnt[14]==2)js[1]+=2,js[2]-=1;//Handling of double kings
cout<<shunzi(0)<<'\n';
}
return 0;
}
reassessment
1. Do not save some very small memory, increase the length of the code, directly pass the array as a form parameter can be reduced by half the length of the recovery.
2. Incomplete thinking, not thinking of a straight after a straight at the beginning, as well as the use of the king bomb as a pair (e.g., three with two with a king bomb), as well as not thinking sufficiently before starting to write.