usaco 3_3_2 shopping offers 题解_leokan的blog.mht

美国USACO题库源程序

 }

/* given an id, calculate the index of it */
int find_item(int id)
 {
  if (itemid[0] =3D=3D id) return 0;
  if (itemid[1] =3D=3D id) return 1;
  if (itemid[2] =3D=3D id) return 2;
  if (itemid[3] =3D=3D id) return 3;
  if (itemid[4] =3D=3D id) return 4;
  return -1;
 }

/* encoding constants 6^0, 6^1, 6^2, ..., 6^5 */
const int mask[5] =3D {1, 6, 36, 216, 1296};

void find_cost(void)
 {
  int p;
  int cst;
  int lv, lv2;
  int amt;
  offer_t *o;
  int i;
  int t;

  /* initialize costs to be infinity */
  for (lv =3D 0; lv < 7776; lv++) cost[lv] =3D 999*25+1;

  /* offer not in heap yet */
  for (lv =3D 0; lv < 7776; lv++) hloc[lv] =3D -1;
 =20
  /* add empty baset */
  cost[0] =3D 0;
  add_heap(0);

  while (hsize)
   {
    /* take minimum basket not checked yet */
    p =3D heap[0];
    cst =3D cost[p];

    /* delete it from the heap */
    delete_min();

    /* try adding each offer to it */
    for (lv =3D 0; lv < noffer; lv++)
     {
      o =3D &offers[lv];
      t =3D p; /* the index of the new heap */
      for (lv2 =3D 0; lv2 < o->nitem; lv2++)
       {
        i =3D o->itemid[lv2];
 /* amt =3D amt of item lv2 already in basket */
 amt =3D (t / mask[i]) % 6;

 if (amt + o->itemamt[lv2] <=3D 5)
   t +=3D mask[i] * o->itemamt[lv2];
 else
  { /* if we get more than 5 items in the basket,
       this is an illegal move */
   t =3D 0; /* ensures we will ignore it, since cost[0] =3D 0 */
   break;
  }
       }
      if (cost[t] > cst + o->cost)
       { /* we found a better way to get this basket */

        /* update the cost */
        cost[t] =3D cst + o->cost;
 add_heap(t); /* add, if necessary, and reheap */
       }
     }
   }
 }

int main(int argc, char **argv)
 {
  FILE *fout, *fin;
  int lv, lv2; /* loop variable */
  int amt[5]; /* goal amounts of each type */
  int a; /* temporary variable */

  if ((fin =3D fopen("shopping.in", "r")) =3D=3D NULL)
   {
    perror ("fopen fin");
    exit(1);
   }
  if ((fout =3D fopen("shopping.out", "w")) =3D=3D NULL)
   {
    perror ("fopen fout");
    exit(1);
   }

  fscanf (fin, "%d", &noffer);

  /* read offers */
  for (lv =3D 0; lv < noffer; lv++)
   {
    fscanf (fin, "%d", &offers[lv].nitem);
    for (lv2 =3D 0; lv2 < offers[lv].nitem; lv2++)
      fscanf (fin, "%d %d", &offers[lv].itemid[lv2], =
&offers[lv].itemamt[lv2]);
    fscanf (fin, "%d", &offers[lv].cost);
   }

  /* read item's information */
  fscanf (fin, "%d", &nitem);
  for (lv =3D 0; lv < nitem; lv++)
    fscanf (fin, "%d %d %d", &itemid[lv], &amt[lv], =
&cost[lv]);

  /* fill in rest of items will illegal data, if necessary */
  for (lv =3D nitem; lv < 5; lv++)=20
   {
    itemid[lv] =3D -1;
    amt[lv] =3D 0;
    cost[lv] =3D 0;
   }

  /* go through offers */
  /* make sure itemid's are of item's in goal basket */
  /* translate itemid's into indexes */
  for (lv =3D 0; lv < noffer; lv++)
   {
    for (lv2 =3D 0; lv2 < offers[lv].nitem; lv2++)
     {
      a =3D find_item(offers[lv].itemid[lv2]);
      if (a =3D=3D -1)
       { /* offer contains an item which isn't in goal basket */
       =20
 /* delete offer */

 /* copy last offer over this one */
        memcpy (&offers[lv], &offers[noffer-1], =
sizeof(offer_t));
 noffer--;

 /* make sure we check this one again */
 lv--;
 break;
       }
      else
        offers[lv].itemid[lv2] =3D a; /* translate id to index */
     }
   }

  /* add in the degenerate offers of buying single items 8/
  for (lv =3D 0; lv < nitem; lv++)
   {
    offers[noffer].nitem =3D 1;
    offers[noffer].cost =3D cost[lv];
    offers[noffer].itemamt[0] =3D 1;
    offers[noffer].itemid[0] =3D lv;
    noffer++;
   }

  /* find the cost for all baskets */
  find_cost();

  /* calculate index of goal basket */
  a =3D 0;
  for (lv =3D 0; lv < 5; lv++)
    a +=3D amt[lv] * mask[lv];

  /* output answer */
  fprintf (fout, "%i\n", cost[a]);
  return 0;
 }
</STRONG></PRE>
      <H2>Slavi Marinov's Comments</H2>
      <P><STRONG>This problem can be solved using dynamic programming. =
This way=20
      is easier to code, and for the test cases it runs for much less =
than 0.1=20
      seconds. </STRONG></P>
      <P><STRONG>We keep a five dimensional array sol (it's not that =
much,=20
      because its size is only 5*5*5*5*5*sizeof(special_offer).) Each=20
      configuration of the dimensions sol[a][b][c][d][e] corresponds to =
having a=20
      products from the first kind, b products from the second kind, c =
from the=20
      third, etc. </STRONG></P>
      <P><STRONG>Basically, the DP forumla is the following :=20
      sol[a][b][c][d][e]=3D min=20
      (a*price[1]+b*price[2]+c*price[3]+d*price[4]+e*price[5], =
so[k].price+=20
      sol[a-so[k].prod[1].items] [b-so[k].prod[2].items] =
[c-so[k].prod[3].items]=20
      [d-so[k].prod[4].items] [e-so[k].prod[5].items] ) where k changes =
from 1=20
      to the number of special offers. Or, in other words, for each =
field of the=20
      array we check which is better : </STRONG></P>
      <UL>
        <LI><STRONG>Not to use any special offer </STRONG>
        <LI><STRONG>To use some special offer </STRONG></LI></UL>
      <P><STRONG>It's very similliar to the knapsack problem. The =
complexity of=20
      this algorithm is O(5*5*5*5*5*100)=3DO(312,500), which is quite =
acceptable.=20
      </STRONG></P><PRE><STRONG>#include &lt;fstream&gt;
#include &lt;cstring&gt;
using namespace std;

ifstream fin ("shopping.in");
ofstream fout("shopping.out");

struct special_offer {
    int n;
    int price;              // the price of that special offer
    struct product {        // for each product we have to keep :
        int id;             // the id of the product
        int items;          // how many items it includes
    } prod[6];
} so[100];                  // here the special offers are kept

int code[1000],             /* Each code is 'hashed' from its real value
                               to a smaller index.  Example :
          If in the input we have code 111, 934, 55,
          1, 66 we code them as 1,2,3,4,5. That is
          kept in code[1000];
                             */

price[6],                   // the price of each product
many[6];                    // how many of each product are to be bought

int s,                      // the number of special offers
    b;                      // the number of different kinds of products =
to be bought

int sol[6][6][6][6][6];     // here we keep the price of each =
configuration

void init() {               // reads the input
    fin&gt;&gt;s;
    for (int i=3D1;i&lt;=3Ds;i++) {
        fin&gt;&gt;so[i].n;
        for (int j=3D1;j&lt;=3Dso[i].n;j++)
            fin&gt;&gt;so[i].prod[j].id&gt;&gt;so[i].prod[j].items;
        fin&gt;&gt;so[i].price;
    }
    fin&gt;&gt;b;
    for (int i=3D1;i&lt;=3Db;i++) {
        int tmp;
        fin&gt;&gt;tmp;
        code[tmp]=3Di; // here we convert the code to an id from 1..5
        fin&gt;&gt;many[i];
        fin&gt;&gt;price[i];
    }
}

void solve() { // the procedure that solves the problem
    for (int a=3D0;a&lt;=3Dmany[1];a++)
        for (int b=3D0;b&lt;=3Dmany[2];b++)
            for (int c=3D0;c&lt;=3Dmany[3];c++)
                for (int d=3D0;d&lt;=3Dmany[4];d++)
                    for (int e=3D0;e&lt;=3Dmany[5];e++)
                        if =
((a!=3D0)||(b!=3D0)||(c!=3D0)||(d!=3D0)||(e!=3D0)) {

      int min=3Da*price[1]+b*price[2]+c*price[3]+d*price[4]+e*price[5];
   /* in min we keep the lowest price at which we can buy a items
      from the 1st type, +b from the 2nd+c of the 3rd... e from the
          5th */

      for (int k=3D1;k&lt;=3Ds;k++) { // for each special offer
          int can=3D1,hm[6];
          memset(&amp;hm,0,sizeof(hm));
          for (int l=3D1;l&lt;=3Dso[k].n;l++)
              hm[code[so[k].prod[l].id]]=3Dso[k].prod[l].items;
             if =
((hm[1]&gt;a)||(hm[2]&gt;b)||(hm[3]&gt;c)||(hm[4]&gt;d)||(hm[5]&gt;e))
                 can=3D0;// we check if it is possible to use that offer

             if (can) {        // if possible-&gt; check if it is better
                               // than the current min
                 int pr=3Dso[k].price+sol[a-hm[1]][b-hm[2]][c-hm[3]]
                          [d-hm[4]][e-hm[5]];
                         /* Those which are not included in the special =
offer */
                 if (pr&lt;min) min=3Dpr;
             }
      }
      sol[a][b][c][d][e]=3Dmin;

                        }
}

int main() {
    memset(&amp;so,0,sizeof(so));
    init();
    solve();
    =
fout&lt;&lt;sol[many[1]][many[2]][many[3]][many[4]][many[5]]&lt;&lt;endl;=

    return 0;
}</STRONG></PRE></DIV></TD></TR></TBODY></TABLE><BR>
<DIV class=3Dopt><A =
title=3D=B2=E9=BF=B4=B8=C3=B7=D6=C0=E0=D6=D0=CB=F9=D3=D0=CE=C4=D5=C2=20
href=3D"http://hi.baidu.com/leokan/blog/category/Oi">=C0=E0=B1=F0=A3=BAOi=
</A> | <A=20
title=3D=BD=AB=B4=CB=CE=C4=D5=C2=CC=ED=BC=D3=B5=BD=B0=D9=B6=C8=CB=D1=B2=D8=
 onclick=3D"return addToFavor();"=20
href=3D"http://cang.baidu.com/do/add" =
target=3D_blank>=CC=ED=BC=D3=B5=BD=CB=D1=B2=D8</A> | =E4=AF=C0=C0(<SPAN=20
id=3Dresult></SPAN>) | <A=20
href=3D"http://hi.baidu.com/leokan/blog/item/5e941cdf0f80fd176227984d.htm=
l#send">=C6=C0=C2=DB</A>&nbsp;(0)
<SCRIPT language=3Djavascript>
/*<![CDATA[*/
var pre =3D [true,'USACO 3.3.1 Riding the Fences =CC=E2=BD=E2', 'USACO =
3.3.1 Riding the Fences =
...','/leokan/blog/item/d8b1bedeb93aa75ccdbf1a10.html'];
var post =3D [true,'USACO 3.3.3 Camelot =CC=E2=BD=E2','USACO 3.3.3 =
Camelot =CC=E2=BD=E2', =
'/leokan/blog/item/5ff69f58f138cada9c820489.html'];
if(pre[0] || post[0]){
	document.write('<div =
style=3D"height:5px;line-height:5px;">&nbsp;</div><div id=3D"in_nav">');
	if(pre[0]){
		document.write('=C9=CF=D2=BB=C6=AA=A3=BA<a href=3D"' + pre[3] + '" =
title=3D"' + pre[1] + '">' +  pre[2] + '</a>&nbsp;&nbsp;&nbsp;&nbsp;');
	}
	if(post[0]){
		document.write('=CF=C2=D2=BB=C6=AA=A3=BA<a href=3D"' + post[3] + '" =
title=3D"' + post[1] + '">' +  post[2] + '</a>');
	}
	document.write('</div>');
}
/*]]>*/
</SCRIPT>
 </DIV>
<DIV class=3Dline></DIV>
<STYLE type=3Dtext/css>#in_related_doc A {
	TEXT-DECORATION: none
}
</STYLE>

<DIV id=3Din_related_tmp></DIV>
<SCRIPT language=3Djavascript type=3Dtext/javascript>
/*<![CDATA[*/
function HI_MOD_IN_RELATED_DOC_CALLBACK(arg){
    if(arg.length <=3D 1) return false;
    var hasMore =3D arg[0];
    var D=3Dfunction(A,B){A[A.length]=3DB;}
    if(arg.length % 2 =3D=3D 0) D(arg, ["","","",""]);

    var html =3D ['<div id=3D"in_related_doc"><div =
class=3D"tit">=CF=E0=B9=D8=CE=C4=D5=C2=A3=BA</div>'];
    D(html, '<table cellpadding=3D"0" cellspacing=3D"3" border=3D"0">');
    for(var i =3D 1, j =3D arg.length; i < j; i +=3D 2){
        D(html, '<tr>');
        D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>&#8226;</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i][3] + =
'/blog/item/' + arg[i][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i][0] + '">' + arg[i][1] + '</a>');
        D(html, new Array(10).join('\u3000'));
        D(html, '</td>');
        if(arg[i + 1][0] !=3D "")
            D(html, '<td width=3D"15px"><a style=3D"font-size:25px" =
>&#8226;</a></td><td><a href=3D"http://hi.baidu.com/' + arg[i + 1][3] + =
'/blog/item/' + arg[i + 1][2] + '.html" target=3D"_blank" title=3D"' + =
arg[i + 1][0] + '">' + arg[i + 1][1] + '</a></td>');
        else
            D(html, '<td>&nbsp;</td><td>&nbsp;</td>');
        D(html, '</tr>');
    }
    if(hasMore) D(html, '<tr><td colspan=3D"4"><a target=3D"_blank" =
href=3D"/sys/search?pageno=3D1&type=3D7&sort=3D1&word=3DUSACO%203%2E3%2E2=
%20Shopping%20Offers%20%CC%E2%BD%E2&item=3D5e941cdf0f80fd176227984d">=B8=FC=
=B6=E0&gt;&gt;</a></td></tr>');
    D(html, '</table></div><div class=3D"line">&nbsp;</div>');

    var div =3D document.getElementById('in_related_tmp');
    if(div){
        div.innerHTML =3D html.join('');
        while(div.firstChild){
            div.parentNode.insertBefore(div.firstChild, div);
        }
        div.parentNode.removeChild(div);
    }
}

if(RelatedDocData =3D=3D -1){	// not supported xhr
    var script =3D document.createElement('script');
    script.type =3D 'text/javascript';
    script.src =3D =
'/sys/search?type=3D8&word=3DUSACO%203%2E3%2E2%20Shopping%20Offers%20%CC%=
E2%BD%E2&item=3D5e941cdf0f80fd176227984d&t=3D' + new Date().getTime();
    document.getElementsByTagName('HEAD')[0].appendChild(script);
}else if(RelatedDocData =3D=3D null){
	GetAndEval =3D true;
}else{
	eval(RelatedDocData);
}

/*]]>*/
</SCRIPT>

<DIV id=3Din_reader>
<DIV class=3Dtit>=D7=EE=BD=FC=B6=C1=D5=DF=A3=BA</DIV>
<SCRIPT>

	var g_spAnnony=3Dtrue;


var g_read=3D[
=09
["match%5Fheaven","17d666726565646f6d626c6573733902","freedombless"],
=09
["yuye%5Fabc","9005797579655f6162633900","yuye_abc"],

{}
];
g_read.length=3Dg_read.length-1;

var _rh1=3D"";
var _rh2=3D"";

function wrreader(){
	_rh1 +=3D '<table width=3D"100%" ><tr>';
	_rh2+=3D'<tr>';
	if(g_spAnnony){
		_rh1+=3D'<td align=3D"center" width=3D"10%" ><img border=3D"0" =
width=3D"55" height=3D"55" =
src=3D"http://img.baidu.com/hi/img/portraitn.jpg"></td>';
		_rh2+=3D'<td>&nbsp;</td>';
		if(g_read.length>0){
			_rh1+=3D'<td align=3D"left" width=3D"12%">';
		}else{
			_rh1+=3D'<td align=3D"left" width=3D"100%">';
		}
		_rh1+=3D"<a =
href=3D'http://passport.baidu.com/?login&tpl=3Dsp&tpl_reg=3Dsp&u=3D"+myre=
f+"' =
target=3D'_self'>=B5=C7=C2=BC</a>=BA=F3=A3=AC=C4=FA=BE=CD=B3=F6=CF=D6=D4=DA=
=D5=E2=C0=EF=A1=A3</td>";
		_rh2+=3D'<td>&nbsp;</td>'