> #include <iostream>
> #include <cstdio>
> #include <cstdlib>
> #include <cstring>
> #include <string>
> #include <algorithm>
> #include <cmath>
> #define INF 999999
> #define N 501
> #define M 101
> using namespace std;
> int m[M],b[M][M],p[M][M],f[N];
> 
> int main()
> {
> 	int nn;
> 	scanf("%d",&nn);
> 	int n,Min,Max;
> 	int k1,k2,km;
> 	int min1,min2,MIN;
> 	int c1,c2;
> 	double ans;
> 	while (nn--)
> 	{
> 		scanf("%d",&n);
> 		Max=-INF;
> 		Min=INF;
> 		for (int i=1;i<=n;i++)
> 		{
> 			scanf("%d",&m[i]);
> 			for (int j=1;j<=m[i];j++)
> 			{
> 				scanf("%d%d",&b[i][j],&p[i][j]);
> 				if (b[i][j]<Min) Min=b[i][j];
> 				if (b[i][j]>Max) Max=b[i][j];
> 			}
> 		}
> 		for (int i=Min;i<=Max;i++) f[i]=INF;
> 		for (int i=1;i<=m[1];i++)
> 			if (f[b[1][i]]>p[1][i]) f[b[1][i]]=p[1][i];
> 		for (int i=2;i<=n;i++)
> 				for (int j=Min;j<=Max;j++)
> 				{
> 					min1=min2=INF;
> 					k1=k2=0;
> 					for (int k=1;k<=m[i];k++)
> 					{
> 						if(b[i][k]>=j&&p[i][k]<min1)
> 						{
> 							k1=k;
> 							min1=p[i][k];
> 						}
> 						if(b[i][k]==j&&p[i][k]<min2)
> 						{
> 							k2=k;
> 							min2=p[i][k];
> 						}
> 					}
> 					if(k1&&f[j]!=INF) c1=f[j]+p[i][k1];
> 					else c1=INF;
> 					MIN=INF;
> 					km=0;
> 					for(int k=j+1;k<=Max;k++)
> 						if(f[k]<MIN)
> 						{
> 							km=k;
> 							MIN=f[k];
> 						}
> 					if(km&&k2) c2=f[km]+p[i][k2];
> 					else c2=INF;
> 					f[j]=c1<c2?c1:c2;
> 				}
> 		ans=0;
> 		for (int i=Min;i<=Max;i++)
> 			if ((f[i]!=INF)&&((double)i/f[i]>ans)) ans=(double)i/f[i];
> 		printf("%.3lf\n",ans);
> 	}
> 	return 0;
> }

• Re:DP题解 (0) hntby 2018-10-04 09:53:42
  • Re:DP题解 (0) boyata 2018-10-04 10:14:17