20160928 ADV

#include "stdafx.h"
#include <stdio.h>
#define MAX_ROW 4
#define MAX_COL 5
#define INT_MAX (int)((unsigned int)~0 >> 1)

int lin_mm[MAX_ROW];
int N,H,V;

int mark[MAX_ROW];
int last_pos;
int last[5];
int d_sum;
int sum;
int m1,m2;
int result;
void tunnel_select(int tunnel)
{
   int i;
   if(tunnel==N+1)
   {
      last_pos=-1;
      d_sum=0;
      sum=0;
      for(i=0;i<MAX_ROW;i++)
      {
         if(mark[i]==1 && last_pos==-1)
         {
            last_pos=i;
            sum+=lin_mm[i];
         }
         else if(mark[i]==1)
         {
            d_sum+=(i-last_pos);
            last_pos=i;
            sum+=lin_mm[i];
         }

      }
      sum+=(m1*m1+m2*m2)*d_sum;
      if(result>sum)
         result=sum;
      return;
   }

   for(i=0;i<V;i++)
   {
      if(tunnel==1 && mark[i]==0)
      {
         mark[i]=1;
         last[tunnel-1]=i;
         tunnel_select(tunnel+1);
         mark[i]=0;
      }
      else if(mark[i]==0 && i-last[tunnel-2] >1)
      {
         mark[i]=1;
         last[tunnel-1]=i;
         tunnel_select(tunnel+1);
         mark[i]=0;
      }
      else
         continue;
   }
   return;
}
int _tmain(int argc, _TCHAR* argv[])
{
    int S[MAX_ROW][MAX_COL];
    int tmp;
    int ind;
    int T;
    int test_case;
    int i,j;
    int v,h;
    int c1,r1;
    int c2,r2;

    freopen("0928adv_tmp.txt", "r", stdin);
    freopen("0928adv_out.txt", "w", stdout);

    setbuf(stdout, NULL);
    scanf("%d", &T);
    for(test_case = 1; test_case <= T; ++test_case)
    {
        result=INT_MAX;
        scanf("%d %d %d", &N,&H,&V);
        for(v=0;v<V;v++)
        {
           for(h=0;h<H;h++)
            scanf("%d ",&S[v][h]);
           lin_mm[v]=INT_MAX;
        }
        scanf("%d %d %d",&c1,&r1,&m1);
        scanf("%d %d %d",&c2,&r2,&m2);
        for(v=0;v<V;v++)
        {
           for(h=0;h<H;h++)
           {
              i=h;
              tmp=0;
              for(j=0;j<i;j++)
              {
                 tmp+=S[v][j]*c1;
              }

              for(j=H-1;j>=i;j--)
              {
                 tmp+=S[v][j]*c2;
              }

              if((H-2*i) > 1)
                  tmp+=(H-2*i - 1)*r2;
              else if((2*i-H)>1)
                  tmp+=(2*i - H - 1)*r1;
              if(lin_mm[v]>tmp)
              {
                 ind = j;
                 lin_mm[v] = tmp;
              }
           }
        }
        tunnel_select(1);
        printf("#%d %d\n",test_case,result);
    }
    return 0;
}

4
1 3 1
42 3 99
4 19 3
4 1 5
1 5 1
1 4 1 3 11
7 2 3
2 6 4
2 5 4
1 4 1 3 11
13 5 1 4 11
1 2 3 4 5
99 2 47 3 31
7 2 3
2 6 5
1 4 1
1 2 3 4
7 3 3
2 9 4


1 4 1 3 11
13 5 1 4 11
1 2 3 4 5
99 2 47 3 31

min = 57, ind=1
min = 92, ind=0
min = 45, ind=2
min = 388, ind=0