Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:DP题解In Reply To:DP题解 Posted by:hntby at 2018-09-24 15:28:54 > #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; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator