HUST ACM新生赛 C题 Chipmunk and Ele. me

 1 #include<bits/stdc++.h>
 2 #pragma GCC optimize(2)
 3 using namespace std;
 4 int c[1001],e[1001],a[1001],b[1001],f[10001],g[10001],vis[10001];
 5 int m,n;
 6 int main(){
 7     cin>>m>>n;
 8     int tot=0;
 9     for(int i=1;i<=m;i++){
10         scanf("%d%d",&c[i],&e[i]);
11         tot+=c[i];
12     }
13     for(int i=1;i<=tot;i++)g[i]=i;
14     for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
15     for(int i=1;i<=m;i++){//第一次dp
16         for(int j=tot;j>=c[i];j--){
17             f[j]=max(f[j],f[j-c[i]]+e[i]);
18         }
19     }
20     double ans=0;
21     for(int i=1;i<=tot;i++)//第二次dp
22         for(int j=1;j<=n;j++)
23             if(i>=a[j])g[i]=min(g[i],g[i-b[j]]);
24     //for(int i=1;i<=tot;i++)cout<<g[i]<<" ";
25     for(int i=1;i<=tot;i++)
26         ans=max(ans,f[i]*1.0/g[i]);
27     cout<<fixed<<setprecision(8)<<ans;
28     return 0;
29 }