2013 ACMICPC 항주 라이브 I 문제

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<cstdio>

#define Maxn 100

using namespace std;

int dp[1<<21],num[Maxn],bag[Maxn][Maxn],g,b,s,now[22];

bool vi[Maxn];

int dfs(int S,int now[])

{

    if(vi[S]) return dp[S];

    if(S==0) return 0;

    int a[22],c[22];

    int i,j,f;

    int ans=-10000000;

    int num=0;

    vi[S]=1;

    memcpy(c,now,sizeof(c));

    for(i=0;i<b;i++){

        if((1<<i)&S){

            for(j=1;j<=g;j++){

                c[j]+=bag[i+1][j];

            }

        }

    }

    for(j=1;j<=g;j++)

        num+=c[j]/s;

    for(i=0;i<b;i++){

        if((1<<i)&S){

            f=0;

            memcpy(a,now,sizeof(a));

            for(j=1;j<=g;j++){

                a[j]+=bag[i+1][j];

                f+=a[j]/s;

                a[j]%=s;

            }

            if(f)

                ans=max(ans,f+dfs(S^(1<<i),a));

            else

                ans=max(ans,num-dfs(S^(1<<i),a));

        }

    }

    return dp[S]=ans;

}

void solve()

{

    int i,j,N;

    N=(1<<b)-1;

    dp[0]=0;

    dfs(N,now);

    int sum=0,cnt[22];

    memset(cnt,0,sizeof(cnt));

    for(i=1;i<=b;i++){

        for(j=1;j<=g;j++){

            cnt[j]+=bag[i][j];

        }

    }

    for(i=1;i<=g;i++)

        sum+=cnt[i]/s;

    printf("%d
",2*dp[N]-sum);

}

int main()

{

    int i,j;

    while(scanf("%d%d%d",&g,&b,&s)!=EOF,g||b||s){

        memset(bag,0,sizeof(bag));

        memset(num,0,sizeof(num));

        memset(dp,-63,sizeof(dp));

        memset(vi,0,sizeof(vi));

        memset(now,0,sizeof(now));

        int x;

        for(i=1;i<=b;i++){

            scanf("%d",&num[i]);

            for(j=1;j<=num[i];j++){

                scanf("%d",&x);

                bag[i][x]++;

            }

        }

        solve();

    }

    return 0;

}

 
사고방식: 기억화 검색.
dp[S]는 남은 상태가 S일 때 기수가 마법석을 최대 얼마나 얻을 수 있는지 나타낸다.