一道卡贪心的题。
也算一道改编题。
此题的解法推荐为二分图的最大匹配。
首先将输入数据转换一下,然后将满足题意的一组牌建立条边,最终边的覆盖数即为 LN 最后可得的分数。
然后求出最大匹配即可。
代码如下:
#include<stdio.h> #include<string.h> char card[30][5]; char s[5]; int map[30][30]; int vis[30]; int link[30]; int k; int find(int a) { for(int i=1; i<=k; i++) { if(!vis[i]&&map[a][i]) { vis[i]=1; if(link[i]==-1||find(link[i])) { link[i]=a; return 1; } } } return 0; } int sum() { int res=0; memset(link,-1,sizeof(link)); for(int i=1; i<=k; i++) { memset(vis,0,sizeof(vis)); if(find(i)) res++; } return res; } void change(char a[]) { if(a[0]=='A') a[0]='0'+14; else if(a[0]=='T') a[0]='0'+10; else if(a[0]=='J') a[0]='0'+11; else if(a[0]=='Q') a[0]='0'+12; else if(a[0]=='K') a[0]='0'+13; if(a[1]=='H') a[1]='4'; else if(a[1]=='S') a[1]='3'; else if(a[1]=='D') a[1]='2'; else if(a[1]=='C') a[1]='1'; } int main() { //freopen("a.txt","r",stdin); //freopen("out.txt","w",stdout); int t; scanf("%d",&t); while(t--) { memset(map,0,sizeof(map)); memset(card,'\0',sizeof(card)); scanf("%d",&k); for(int i=1; i<=k; i++) scanf("%*c%s",card[i]); //printf("**\n"); for(int i=1; i<=k; i++) { scanf("%*c%s",s); for(int j=1; j<=k; j++) { change(card[j]); change(s); if(s[0]>card[j][0]) map[i][j]=1; else if(s[0]==card[j][0]&&s[1]>card[j][1]) map[i][j]=1; //printf("**%d\n",map[i][j]); } } int res=sum(); printf("%d\n",res); } return 0; }