p4377 [USACO18OPEN]Talent Show-白红宇

p4377 [USACO18OPEN]Talent Show

阅读量：6477 次

发布时间：2019-06-23

本文共 846 字，大约阅读时间需要 2 分钟。

分析

经典的01分数规划问题

用01背包check即可

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;#define int long longstruct node { int w,t;};node d[1100];int dp[1100000],n,m;inline bool go(int mid){ int i,j,k; memset(dp,-0x3f,sizeof(dp)); dp[0]=0; for(i=1;i<=n;i++) for(j=m;j>=0;j--) dp[min(m,j+d[i].w)]= max(dp[j]+d[i].t-d[i].w*mid,dp[min(m,j+d[i].w)]); return dp[m]>=0;}signed main(){ int i,j,s1=0,s2=0; scanf("%d%d",&n,&m); for(i=1;i<=n;i++){ scanf("%d%d",&d[i].w,&d[i].t); d[i].t*=1000; } int le=0,ri=1000001; while(ri-le>1){ int mid=(le+ri)>>1; if(go(mid))le=mid; else ri=mid; } cout<