2013 hangzhou regional I题

感觉最近写代码总是小错误不断,没有刚学acm时认真了。。

#include<stdio.h>
#include<string.h>
int box[30][10];
int dp[1<<21];
int g,b,s,goal;
inline int max(int a,int b){return a>b?a:b;}
int DP(int st)
{
    int i,j,k;
    if(dp[st]!=-1) return dp[st];
    int co[10];
    memset(co,0,sizeof(co));
    for(i=0;i<=b-1;i++)
    {
        if(!(st&(1<<i))) continue;
        for(j=1;j<=g;j++) co[j]+=box[i][j];
    }
    int sr=0;
    for(i=1;i<=g;i++)
    {
        sr+=co[i]/s;
        co[i]=co[i]%s;
    }
    int rest=goal-sr;
    for(i=0;i<=b-1;i++)
    {
        if(st&(1<<i)) continue;
        int score=0,tmpc[10];
        for(j=1;j<=g;j++) tmpc[j]=co[j];
        for(j=1;j<=g;j++)
        {
            tmpc[j]+=box[i][j];
            score+=tmpc[j]/s;
        }
        if(score)
        {
            dp[st]=max(dp[st],score+DP(st|(1<<i)));
        }
        else
        {
            dp[st]=max(dp[st],rest-DP(st|(1<<i)));
        }
    }
    return dp[st];
}
int main()
{
    int i,j;

    while(~scanf("%d%d%d",&g,&b,&s) && !(g==0 && b==0 && s==0))
    {
        memset(dp,-1,sizeof(dp));
        memset(box,0,sizeof(box));
        dp[(1<<b)-1]=0;
        for(i=0;i<=b-1;i++)
        {
            int n;
            scanf("%d",&n);
            for(j=1;j<=n;j++)
            {
                int c;
                scanf("%d",&c);
                box[i]1++;
            }
        }
        goal=0;
        int col[10];memset(col,0,sizeof(col));
        for(i=0;i<=b-1;i++)
            for(j=1;j<=g;j++)
                col[j]+=box[i][j];
        for(j=1;j<=g;j++)
            goal+=col[j]/s;
        printf("%d\n",2*DP(0)-goal);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>