I haven't tried this and have no idea if this would work but I would try something this in link_summary.tpl
Code:
{if $pagename eq "story"}
{if $cat_array[thecat].dogs}
<----Advertisement about dogs----->
{/if}{/if}
{if $pagename eq "story"}
{if $cat_array[thecat].birds}
<---Advertisement about birds------>
{/if}{/if}
and so on...