1018.txt

pku acm 1018 AC代码

刚开始还以为是个动态规划题(但网上大家公认此题的dp 相当困难,似乎没有用 dp 实现的),我用和poj 1163 完全一样的方法实现,,wa 了.最后用搜索做出来了,先确定 brand 的范围,然后以之搜索,我没有做任何优化.

代码如下:

#include <stdio.h>
#define MINP 1000000;

int main(){
    int t,n;
    int val[101][101][2];
    int mi[101];
    int b[10001],bn;
    int tp;
    int lt,ll,kk;
    int minp,check;
    double maxbp,tmp;
    
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        bn=1;
        for(lt=1;lt<=n;lt++){
            scanf("%d",&mi[lt]);
            for(ll=1;ll<=mi[lt];ll++){
                scanf("%d %d",&val[lt][ll][0],&val[lt][ll][1]);
                b[bn]=val[lt][ll][0];
                bn++;
            }
        }
        maxbp=0;
        for(lt=1;lt<bn;lt++){
            tp=0;
            for(ll=1;ll<=n;ll++){
                minp=MINP;
                check=0;
                for(kk=1;kk<=mi[ll];kk++){
                    if(val[ll][kk][0]>=b[lt]&&val[ll][kk][1]<minp){
                        minp=val[ll][kk][1];
                        check=1;
                    }
                }
                if(check){
                    tp+=minp;
                }
                else
                    break;
            }
            if(check){
                tmp=b[lt]/(double)tp;
                if(tmp>maxbp)
                    maxbp=tmp;
            }
        }
        printf("%.3f\n",maxbp);
    }
}