压缩状态的动态规划

因为带宽的范围比较大，但数量不是很大（<=10000）
所以将带宽排序，压缩一下状态进行动归

附一遍AC代码

#include<iostream>
using namespace std;
int i,j,x,y,k,n,m[102],a[102][102],o,
d[100002][2],t,e[102][102];
double f[102][10002],an,c[100002],b[102][102],yy;
void sort(int l,int r)
{int p,q;
double mid;
p=l;q=r;mid=c[(p+q)/2];
while (1==1)
{while (c[p]<mid)p++;
while (c[q]>mid)q--;
if (p<=q)
{yy=c[p];c[p]=c[q];c[q]=yy;
y=d[p][0];d[p][0]=d[q][0];d[q][0]=y;
y=d[p][1];d[p][1]=d[q][1];d[q][1]=y;
p++;q--;}
 if (p>q)break;     
       }
       if (p<r)sort(p,r);
       if (q>l)sort(l,q);
     
     
     
     }
int main()
{
cin>>t;
while (t>0)
{t--;
cin>>n;o=0;
for (i=1;i<=n;i++)
{cin>>m[i];
for (j=1;j<=m[i];j++)
{cin>>a[i][j]>>b[i][j];o++;c[o]=a[i][j];d[o][0]=i;d[o][1]=j;}
}
sort(1,o); 
y=0;
 for (i=1;i<=o;i++)
 {e[d[i][0]][d[i][1]]=y;c[y]=c[i];if (c[i]!=c[i+1]&&i!=o)y++;}
 for (i=1;i<=n;i++)
 for (j=0;j<=y;j++)
 f[i][j]=-1;

for (i=1;i<=m[1];i++)
if (f[1][e[1][i]]<b[1][i]/c[e[1][i]])
f[1][e[1][i]]=b[1][i]/c[e[1][i]]; 
 for (i=2;i<=n;i++)
 for (j=1;j<=m[i];j++)
 {for (k=0;k<=e[i][j];k++)
 if (f[i-1][k]>0)
 if (f[i][k]>f[i-1][k]+b[i][j]/c[k]||f[i][k]==-1)
     f[i][k]= f[i-1][k]+b[i][j]/c[k];
     for (k=e[i][j]+1;k<=y;k++)
     if (f[i-1][k]>0)
 if (f[i][e[i][j]]>f[i-1][k]*c[k]/c[e[i][j]]+b[i][j]/c[e[i][j]]
 ||f[i][e[i][j]]==-1)
     f[i][e[i][j]]= f[i-1][k]*c[k]/c[e[i][j]]+b[i][j]/c[e[i][j]];
       }
       an=0;
       for(i=0;i<=y;i++)
       if (f[n][i]!=-1)
       if (f[n][i]<an||an==0)an=f[n][i];
       printf("%.3f",1/an);
       cout<<endl;
      
      }
 }