【题解】洛谷P2668(P2540)[NOIP2015]斗地主(增强版) 线性DP+dfs
终于看明白了大佬题解,然而还是各种错误。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define _rep(i,a,b) for(int i=(a);i<=(b);i++)
int t,n,ans,dp[25][25][25][25][3],p[25],cnt[6];
//dp[a][b][c][d][e],a个单张,b个两张,c个三张,d个四张,e个王的最小出牌次数
void Init()//dp预处理出最小操作次数
{
memset(dp,0x3f,sizeof(dp));dp[0][0][0][0][0]=0;
_rep(d,0,n)_rep(c,0,n)_rep(a,0,n)_rep(b,0,n)_rep(e,0,2)//循环顺序很重要
{
int tmp=100;
if(a>0)tmp=min(tmp,dp[a-1][b][c][d][e]+1);
if(b>0)tmp=min(tmp,dp[a][b-1][c][d][e]+1);
if(c>0)tmp=min(tmp,dp[a][b][c-1][d][e]+1);
if(d>0)tmp=min(tmp,dp[a][b][c][d-1][e]+1);
if(e>0)tmp=min(tmp,dp[a][b][c][d][e-1]+1);
//先走单张
if(e>1)tmp=min(tmp,dp[a][b][c][d][e-2]+1);
//王炸
if(a>0&&c>0)tmp=min(tmp,dp[a-1][b][c-1][d][e]+1);
if(c>0&&e>0)tmp=min(tmp,dp[a][b][c-1][d][e-1]+1);
//三带一
if(b>0&&c>0)tmp=min(tmp,dp[a][b-1][c-1][d][e]+1);
//三带二
if(a>1&&d>0)tmp=min(tmp,dp[a-2][b][c][d-1][e]+1);
if(a>0&&d>0&&e>0)tmp=min(tmp,dp[a-1][b][c][d-1][e-1]+1);
if(d>0&&e>1)tmp=min(tmp,dp[a][b][c][d-1][e-2]+1);
if(b>0&&d>0)tmp=min(tmp,dp[a][b-1][c][d-1][e]+1);
if(b>1&&d>0)tmp=min(tmp,dp[a][b-2][c][d-1][e]+1);
if(d>1)tmp=min(tmp,dp[a][b][c][d-2][e]+1);
//四带二
if(c>0)tmp=min(tmp,dp[a+1][b+1][c-1][d][e]);
if(d>0)tmp=min(tmp,dp[a+1][b][c+1][d-1][e]);
//拆牌
dp[a][b][c][d][e]=min(dp[a][b][c][d][e],tmp);
}
}
void dfs(int step)
{
if(step>=ans)return;
int len;bool flag;
_rep(k,1,3)_rep(i,1,12)
{
flag=true;
if(k==1)len=5;//顺子
if(k==2)len=3;//连对
if(k==3)len=2;//飞机
while(flag&&i+len-1<=12)
{
_rep(j,1,len)if(p[i+j-1]<k){flag=false;break;}
if(!flag)continue;
_rep(j,1,len)p[i+j-1]-=k;
dfs(step+1);
_rep(j,1,len)p[i+j-1]+=k;
len++;//尝试更长的顺子连对飞机
}
}
cnt[1]=cnt[2]=cnt[3]=cnt[4]=cnt[5]=0;_rep(i,1,13)cnt[p[i]]++;
cnt[5]=p[14];
ans=min(ans,step+dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]][cnt[5]]);
}
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d%d",&t,&n);
Init();
while(t--)
{
memset(p,0,sizeof(p));ans=n;
_rep(i,1,n)
{
int num,col;scanf("%d%d",&num,&col);
if(num==0){p[14]++;continue;}
if(num>=3)p[num-2]++;
if(num==2)p[13]++;
if(num==1)p[12]++;
}
dfs(0);printf("%d\n",ans);
}
return 0;
}
总结
牛批的爆搜