A-C:
惯例是宝宝题,会打暴力就能过哈
D:
其实也是暴力dfs,有一个double打错成int(我是猪鼻),卡了我很久
#include<bits/stdc++.h>
using namespace std;const int maxn = 1e3 + 10,eps=1e-7;
int n,s,t;
bool vis[10];
double sum=1e8;
struct Node{double x,y,x1,y1;
}a[maxn];
double dis(double x,double y,double x1,double y1){return sqrt(1.0*(x-x1)*(x-x1)+1.0*(y-y1)*(y-y1));
}
void dfs(double sm,int x,int y){int cnt=0;for(int i=1;i<=n;i++){if(!vis[i]){vis[i]=1;double tmp=dis(a[i].x,a[i].y,x,y);dfs(sm+tmp,a[i].x1,a[i].y1);tmp=dis(a[i].x1,a[i].y1,x,y);dfs(sm+tmp,a[i].x,a[i].y);vis[i]=0;}else cnt++;}if(cnt==n){if(sm-sum<eps)sum=sm;return;}
}
signed main(){cin>>n>>s>>t;double ans=0;for(int i=1;i<=n;i++){double x,y,x1,y1;cin>>x>>y>>x1>>y1;ans+=dis(x,y,x1,y1);a[i].x=x,a[i].y=y,a[i].x1=x1,a[i].y1=y1;}for(int i=1;i<=n;i++){vis[i]=1;double tmp=dis(0,0,a[i].x,a[i].y);dfs(tmp,a[i].x1,a[i].y1);tmp=dis(0,0,a[i].x1,a[i].y1);dfs(tmp,a[i].x,a[i].y);vis[i]=0;}ans=ans*1.0/t+sum*1.0/s;printf("%.7lf",ans);
}
E:
一开始以为是dp想了很久想不通。后来才发现是经典二分+DP。不过check部分还是要思考一下,要求生产数量大于mid在最优情况下能否实现。一种机器严格优于另一种机器是在\(A_i*B_i\)的条件下才会具备的,在这个结论下我们也会思考去先求出最大可取值k再暴力枚举剩下的部分。
这个做法是过不了hack数据的,因为我们并不能直接枚举剩余部分,剩余部分其实是不确定的(可能只取k-1然后再枚举取AB更优),所以做法最终为枚举剩余部分(最多只有ai或者bi个,因为超过一定换成更优的)用某个机器生产,剩下的用另一个机器生产的最小值。
代码很丑,建议看官解代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define mkp make_pair
#define pii pair<int,int>
#define int long long
using namespace std;
const int maxn=200;
int a[maxn],p[maxn],b[maxn],q[maxn],n,x;
bool jud(int mid){int sum=0;for(int i=1;i<=n;i++){int k=mid/(a[i]*b[i]);int res=mid-k*a[i]*b[i];int ans=1e18,ans2=1e18;int tte=0;for(int j=0;j<=b[i];j++){for(int m=0;m<=a[i];m++){if(a[i]*j+b[i]*m>=res)ans=min(ans,p[i]*j+m*q[i]);}}tte=ans+k*p[i]*b[i];if(k>0){res=mid-(k-1)*a[i]*b[i];for(int j=0;j<=b[i];j++){for(int m=0;m<=a[i];m++){if(a[i]*j+b[i]*m>=res)ans2=min(ans2,p[i]*j+m*q[i]);}}tte=min(ans2+(k-1)*p[i]*b[i],tte);}sum+=tte;//if(mid==4)cout<<p[i]<<' '<<sum<<endl;}if(sum<=x)return 1;else return 0;
}
signed main(){cin>>n>>x;for(int i=1;i<=n;i++){cin>>a[i]>>p[i]>>b[i]>>q[i];int v1=b[i]*p[i],v2=a[i]*q[i];if(v1>v2)swap(a[i],b[i]),swap(p[i],q[i]);}int l=0,r=1e9+7,mid=(l+r+1)/2;while(l<r){if(jud(mid))l=mid;else r=mid-1;mid=(l+r+1)/2;}cout<<mid<<endl;
}
F:
DP吧。不会