学步园

定义状态dp[i][s]表示把雇佣前i个应聘者到达s这个状态的最小费用

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX = 6e8;
const int N = 6561*3;
int dp[N],num_s[10],top,fare,s,n,m,pow_3[10];
int num_convert()//把数组转化为10进制整数
{
    int ans=0,pow=1;
    for(int i=1;i<=s;i++)
    {
        if(num_s[i]>=2)
        {
            ans+=2*pow;
        }
        else
        {
            ans+=num_s[i]*pow;
        }
        pow*=3;
    }
    return ans;
}
void str_convert(char *ss)//把输入的字符串变为数组的形式
{
    char *p=ss;
    int ans,flag=0;
    while(*p!='\0')
    {
        ans=0;
        while(*p==' ')
            p++;
        while(*p!='\0'&&'0'<=*p&&*p<='9')
        {
            ans=ans*10+*p-'0';
            p++;
        }
        if(ans)
        {
            if(flag)
            {
                num_s[ans]++;
            }
            else
            {
                fare+=ans;
                flag=1;
            }
        }
    }
}
int fun(int d)//数和数组相加
{
    top=1;
    while(d)
    {
        num_s[top++]+=d%3;
        d/=3;
    }
    return num_convert();
}
int main()
{
    pow_3[0]=1;
    for(int i=1;i<9;i++)
    {
        pow_3[i]=pow_3[i-1]*3;
    }
    char ss[100];
    while(scanf("%d %d %d",&s,&n,&m)!=EOF&&s)
    {
        getchar();
        fill(dp,dp+pow_3[s],MAX);
        memset(num_s,0,sizeof(num_s));
        fare=0;
        for(int i=0;i<n;i++)//累积前n项的和
        {
            gets(ss);
            str_convert(ss);
        }
        int number=num_convert();
        dp[number]=fare;
        for(int i=1;i<=m;i++)
        {
            gets(ss);
            for(int j=pow_3[s]-1;j>=0;j--)
            {
                fare=0;
                memset(num_s,0,sizeof(num_s));
                str_convert(ss);
                number=fun(j);
                dp[number]=min(dp[number],dp[j]+fare);
            }
        }
        printf("%d\n",dp[pow_3[s]-1]);
    }
    return 0;
}