지주

7591 단어
2015 마지막 문제, 이 문제는 대폭검색+욕심입니다. 먼저 4대 1, 3대 1, 단패, etc를 열거한 다음에 순자 최적화를 열거합니다. 검색 최적화의 해답이 최적화된 것인지 아닌지(반드시 가장 좋은 것은 아니므로 귀속해야 합니다), 귀속해서 다른 순자 최적화를 찾습니다.색깔 얘기하는데 무슨 소용이야.
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int t,n;int s[5]; int a[9999],b[9999];int ans=23;
void dfs(int x){
    if(ans<x)return ;
    memset(s,0,sizeof(s));
    for(int i=1;i<=14;i++) 
    {
        if(a[i]==1||a[i]==2)
        s[a[i]]++;
    }// 
    for(int i=2;i<=14;i++)
    {
        if(a[i]==4)
        {
            s[4]++;
            if(s[1]>=2) s[1]-=2;
            else if(s[2]>=2) s[2]-=2;
            else if(s[2]>=1) s[2]--;
        }   
    }// ...
    for(int i=2;i<=14;i++)
    {
        if(a[i]==3)
        {
            s[3]++;
            if(s[1]>=1) s[1]--;
            else if(s[2]>=1) s[2]--;
        }
    }// 。。。。
    int w=0;
    for(int i=1;i<=4;i++)
    w+=s[i];// 
    ans=min(ans,x+w);
    int j;
    for(int i=3;i<=10;i++)// 
    {
        for( j=i;j<=14;j++)
        {
            a[j]--;
            if(a[j]<0)break;
            if(j-i>=4) dfs(x+1);// 
        }
        if(j==15)j--;
        while(j>=i)a[j--]++;// 
    }
        for(int i=3;i<=12;i++)// 
    {
        for( j=i;j<=14;j++)
        {
            a[j]-=2;
            if(a[j]<0) break;
            if(j-i>=2) dfs(x+1);
        }
        if(j==15) j--;
        while(i<=j) a[j--]+=2;
    }
        for(int i=3;i<=13;i++)// 
    {
        for( j=i;j<=14;j++)
        {
            a[j]-=3;
            if(a[j]<0)break;
            if(j-i>=1) dfs(x+1);
        }
        if(j==15) j--;
        while(i<=j) a[j--]+=3;
    }
    return ;
} 
int main(){
    scanf("%d%d",&t,&n);
    for(int i=1;i<=t;i++)
    {
        memset(a,0,sizeof(a)); 
        for(int i=1;i<=n;i++)
        {
            int x;
            scanf("%d%d",&x,&b[i]);
            if(x==1)a[14]++;
            else if(x==0)a[1]++;
            else a[x]++;
        }
        ans=14;// 14
        dfs(0);
        printf("%d
"
,ans); } }

좋은 웹페이지 즐겨찾기