LOJ2422 NOIP2015 斗地主 【搜索+贪心】*
2024-10-21 14:31:14
LOJ2422 NOIP2015 斗地主
题目大意很简单,就是问你斗地主的一分手牌最少多少次出完
然后我们发现对于一种手牌状态,不考虑顺子的情况是可以贪心做掉的
然后我们直接枚举一下顺子出牌情况就可以了
LOJ上的数据随便写点基本贪心就行了
如果想过UOJ上的加强版的话还是把中间那一部分毒瘤的特判更优情况加上吧
当然也有个Smallfat大神用DP做掉的
我感觉DP更严谨一些,但是毕竟贪心好写嘛
#include<bits/stdc++.h>
using namespace std;
#define N 20
int n,ans,is;
int col[N],cnt[N],tmp[N];
int cal(){
for(int i=;i<=;i++)tmp[i]=cnt[i];
int res=;
while(tmp[]&&tmp[]>=)res++,tmp[]--,tmp[]-=;
while(tmp[]&&tmp[]>=)res++,tmp[]--,tmp[]-=;
//
while(tmp[]&&!tmp[]&&tmp[]>=&&tmp[]) res+=,tmp[]--,tmp[]-=,tmp[]--;
while(!tmp[]&&tmp[]&&tmp[]>=&&!tmp[]) res+=,tmp[]--,tmp[]-=;
while(tmp[]&&tmp[]&&tmp[]&&tmp[]>=) res+=,tmp[]--,tmp[]--,tmp[]--,tmp[]-=;
while(tmp[]&&tmp[]&&!tmp[]&&tmp[]>=) res+=,tmp[]--,tmp[]--,tmp[]-=;
while(!tmp[]&&!tmp[]&&tmp[]>=&&tmp[]>=)res+=,tmp[]-=,tmp[]-=;
while(!tmp[]&&!tmp[]&&tmp[]>=&&tmp[]) res+=,tmp[]-=,tmp[]--;
//
while(tmp[]&&tmp[])res++,tmp[]--,tmp[]--;
while(tmp[]>=)res++,tmp[]-=;
while(tmp[]&&tmp[])res++,tmp[]--,tmp[]--;
while(tmp[]&&tmp[])res++,tmp[]--,tmp[]--;
if(is&&tmp[]>=)tmp[]-=,res++;
return res+tmp[]+tmp[]+tmp[]+tmp[];
}
bool check(int l,int r,int num){
for(int i=l;i<=r;i++)if(col[i]<num)return ;
return ;
}
void modify(int l,int r,int num){
for(int i=l;i<=r;i++){
cnt[col[i]]--;
col[i]+=num;
cnt[col[i]]++;
}
}
void dfs(int step){
if(step>=ans)return;
ans=min(ans,step+cal());
for(int l=;l<=;l++){
for(int len=;len+l-<=;len++){
int r=len+l-;
if(!check(l,r,))break;
modify(l,r,-);
dfs(step+);
modify(l,r,);
}
}
for(int l=;l<=;l++){
for(int len=;len+l-<=;len++){
int r=len+l-;
if(!check(l,r,))break;
modify(l,r,-);
dfs(step+);
modify(l,r,);
}
}
for(int l=;l<=;l++){
for(int len=;len+l-<=;len++){
int r=len+l-;
if(!check(l,r,))break;
modify(l,r,-);
dfs(step+);
modify(l,r,);
}
}
}
void solve(){
int op,x;ans=n;
for(int i=;i<=;i++)col[i]=,cnt[i]=;
for(int i=;i<=n;i++){
scanf("%d%d",&op,&x);
if(op>)op--;
else if(op)op=;
col[op]++;
}
for(int i=;i<=;i++)if(col[i])cnt[col[i]]++;
cnt[]+=col[];
is=(col[]==);
dfs();
printf("%d\n",ans);
}
int main(){
int T;scanf("%d%d",&T,&n);
while(T--)solve();
return ;
}
最新文章
- Node.js 教程 02 - 经典的Hello World
- Percona TokuDB
- .NET Core与.NET Framework、Mono之间的关系
- LeetCode-Search in Rotated Sorted Array II
- PHP数据库操作:从MySQL原生API到PDO
- JS 打印功能代码可实现打印预览、打印设置等
- createStatement()的用法
- register instruction pointer
- VS2005内存泄漏检测方法[转载]
- 在ECSHOP首页今日特价(促销商品)增加倒计时效果
- Unix/Linux环境C编程入门教程(24) MySQL 5.7.4 for Red Hat Enterprise 7(RHEL7)的安装
- 开发环境配置--Ubuntu+Qt4+OpenCV(二)
- 201521123013 《Java程序设计》第7周学习总结
- (转载)Unity UGUI鼠标点击UI不受影响方法IsPointerOverGameObject
- grafna与饼状图
- win10安装windows live writer 错误:OnCatalogResult:0x80190194
- mysql5.7忘记密码时,修改root密码
- [LeetCode&;Python] Problem 617. Merge Two Binary Trees
- PS使用技巧
- Linux应用小技巧