悬棺
查看原帖
悬棺
1256790
X_m_X楼主2025/7/3 16:38

82pts,Wa On 10,12,13,14,15,16,20,22,49. code

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
//#define endl "\n"
//#define int long long
#define ii inline
//#define fro(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
#define rint register int
//#define INF (int)(1e18)
#define lowbit(x) (x&(-x))
using namespace std;
const int N=2e6+5;
int n,T;
int ans;
int now[25];
int dp[30][30][30][30];
ii void dfs(int x){
	if(x>=ans)return;
	//--------------------------//other
	int one=0,tow=0,th=0,four=0;
	for(rint i=2;i<=14;i++){
		if(now[i]==1)one++;
		if(now[i]==2)tow++;
		if(now[i]==3)th++;
		if(now[i]==4)four++;
	}
	if(now[0]==0){
		ans=min(ans,x+dp[one][tow][th][four]);
	}
	else if(now[0]==1){
		ans=min(ans,x+dp[one+1][tow][th][four]);
	}else{
		ans=min(ans,x+dp[one][tow][th][four]+1);
		ans=min(ans,x+dp[one+2][tow][th][four]);
	}
	int flag;
	//-------------------------//单顺子
	flag=0;
	for(rint i=3;i<=14;i++){
		if(now[i]<1)flag=0;
		else{
			flag++;
			if(flag>=5){
				for(rint j=i;j>=i-flag+1;j--)now[j]-=1;
				dfs(x+1);
				for(rint j=i;j>=i-flag+1;j--)now[j]+=1;
			}
		}
	}
	//-------------------------//双顺子
	flag=0;
	for(rint i=3;i<=14;i++){
		if(now[i]<2)flag=0;
		else{
			flag++;
			if(flag>=3){
				for(rint j=i;j>=i-flag+1;j--)now[j]-=2;
				dfs(x+1);
				for(rint j=i;j>=i-flag+1;j--)now[j]+=2;
			}
		}
	}
	//-------------------------//三顺子
	flag=0;
	for(rint i=3;i<=14;i++){
		if(now[i]<3)flag=0;
		else{
			flag++;
			if(flag>=2){
				for(rint j=i;j>=i-flag+1;j--)now[j]-=3;
				dfs(x+1);
				for(rint j=i;j>=i-flag+1;j--)now[j]+=3;
			}
		}
	}
}
signed main(){
	IOS
//	fro("");
	cin>>T>>n;
	memset(dp,0x3f,sizeof dp);
	dp[0][0][0][0]=0;
	for(rint l=0;l<=5;l++){
		for(rint k=0;k<=7;k++){
			for(rint j=0;j<=11;j++){
				for(rint i=0;i<=23;i++){
					if(i*1+j*2+k*3+l*4>n)continue;
					if(i>0)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k][l]+1);//
					if(j>0)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i][j-1][k][l]+1);//
					if(k>0)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i][j][k-1][l]+1);//
					if(l>0)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i][j][k][l-1]+1);//
					if(i>0 && k>0)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-1][j][k-1][l]+1);//
					if(j>0 && k>0)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i][j-1][k-1][l]+1);//
					if(i>1 && l>0)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i-2][j][k][l-1]+1);//
					if(j>1 && l>0)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i][j-2][k][l-1]+1);//
					if(j>0)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i+2][j-1][k][l]);//
					if(k>0)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i+1][j+1][k-1][l]);//
					if(l>0)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i+1][j][k+1][l-1]);//
					if(l>0)dp[i][j][k][l]=min(dp[i][j][k][l],dp[i][j+2][k][l-1]);//
				}
			}
		}
	}
	while(T--){
		memset(now,0,sizeof now);
		ans=n;
		for(rint i=1;i<=n;i++){
			int op1,op2;
			cin>>op1>>op2;
			if(op1==1)now[14]++;
			else now[op1]++;
		}
		dfs(0);
		cout<<ans<<"\n";
	}
}
2025/7/3 16:38
加载中...