poj 1018 dp

本文主要是介绍poj 1018 dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<cstdio>
#include<cstring>
#define INF 0x3f3f3f3f
#define MAX(x,y) ((x)>(y)?(x):(y))
#define MIN(x,y) ((x)>(y)?(y):(x))
int dp[120][400];
int main()
{int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);memset(dp,0x3f,sizeof(dp));for(int i=1;i<=n;i++){int num;scanf("%d",&num);while(num--){int b,p;scanf("%d%d",&b,&p);if(i==1){dp[i][b]=MIN(dp[i][b],p);}else{for(int k=1;k<=400;k++){if(dp[i-1][k]!=INF){if(b>=k)dp[i][k]=MIN(dp[i][k],dp[i-1][k]+p);elsedp[i][b]=MIN(dp[i][b],dp[i-1][k]+p);}}}}}double res=0;for(int i=0;i<=400;i++){if(dp[n][i]!=INF){res=MAX(res,(double)i/dp[n][i]);}}printf("%.3lf\n",res);}
}

这篇关于poj 1018 dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---