lightoj1037

CODE

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int hl[16];
int g[16][16];
int dp[1<<15];
int ncase;
int main()
{
        int t;
        scanf("%d",&t);
        while(t--)
        {
                memset(dp,0x3f,sizeof(dp));
                dp[0]=0;
                int n;
                scanf("%d",&n);
                for(int i=0;i<n;i++)
                {
                        scanf("%d",hl+i);
                }
                for(int i=0;i<n;i++)
                        for(int j=0;j<n;j++)
                        {
                                scanf ("%1d",&g[i][j]);
                        }
                for(int s=0;s<(1<<n)-1;s++)
                {
                        for(int i=0;i<n;i++)
                        {
                                if(s&(1<<i))continue;
                                int tp=0x3f3f3f3f;
                                for(int j=0;j<n;j++)
                                {
                                        if((s&(1<<j))==0||g[j][i]==0)continue;
                                        int time=(hl[i]+g[j][i]-1)/g[j][i];
                                        tp=min(tp,time);
                                }
                                if(tp==0x3f3f3f3f)
                                {
                                        dp[s|(1<<i)]=min(dp[s|(1<<i)],dp[s]+hl[i]);
                                }
                                else
                                        dp[s|(1<<i)]=min(dp[s|(1<<i)],dp[s]+tp);
                        }

                }
                cout << "Case "<<++ncase<<": "<<dp[(1<<n)-1]<<endl;
        }
        return 0;
}