设数组answer【110】【10010】，a【i】【j】表示前i个物品最小带宽为j时的最小总和（前提是假设带宽不超过10000），详见代码。
#include <stdio.h>
typedef struct
{
 int band,price;
}Node;
Node array[110][110];
int answer[110][10010];
int num,number[110];
double result;
void initial();
void dp();
void deal();
void initial()
{
 int i,j;
 scanf("%d",&num);
 for(i=1;i<=num;i++)
 {
  scanf("%d",&number[i]);
  for(j=1;j<=number[i];j++)
   scanf("%d%d",&array[i][j].band,&array[i][j].price);
 }
 for(i=1;i<=num;i++)
	 for(j=1;j<=10000;j++)
		 answer[i][j]=99999;
 for(i=1;i<=number[1];i++)
  if(array[1][i].price<answer[1][array[1][i].band])
	 answer[1][array[1][i].band]=array[1][i].price;
}
void dp()
{
 int i,j,k,temp,min;
 for(i=1;i<=num-1;i++)
	 for(j=1;j<=10000;j++)
	 {
      if(answer[i][j]!=99999)
	  {
       for(k=1;k<=number[i+1];k++)
	   {
         min=j;
		 if(array[i+1][k].band<min)
			 min=array[i+1][k].band;
         temp=answer[i][j]+array[i+1][k].price;
		 if(temp<answer[i+1][min])
			 answer[i+1][min]=temp;
	   }
	  }
	 }
}
void deal()
{
 int i;
 double temp;
 result=0;
 for(i=1;i<=10000;i++)
 if(answer[num][i]!=99999)
 {
  temp=(double)i/(double)answer[num][i];
  if(temp>result) result=temp;
 }
 printf("%.3f\n",result);
}
int main()
{
 int cases;
 scanf("%d",&cases);
 while(cases--)
 {
  initial();
  dp();
  deal();
 }
 return 0;
}
据说此题数据很水，虽然过了，但还是可能出现错误，希望到时有高人指正。飘过。。。。。。。。。

• Re:题意和贪心思路 (37) chong_boy 2010-11-07 13:17:38