郑州建设网站企业,如何提高网站索引量,搭建网站免费空间,王稳庄网站建设题目
登录—专业IT笔试面试备考平台_牛客网 n(n20)本书#xff0c;放在桌子上#xff0c;
第i本书的可以看成是li(li1e3)*1*1的物体#xff0c;其中长为li#xff0c;宽为1#xff0c;高为1#xff0c;
质量均匀分布#xff0c;且为wi(wi1e3)
求n本书摞…题目
登录—专业IT笔试面试备考平台_牛客网 n(n20)本书放在桌子上
第i本书的可以看成是li(li1e3)*1*1的物体其中长为li宽为1高为1
质量均匀分布且为wi(wi1e3)
求n本书摞在一起使得任意一本书都不掉下桌子时书能伸出桌沿的长度的最大值是多少
思路来源
官方题解申老师
题解 放的话肯定是从上往下放这样已经放上去的可以看成是一个物体 并且当b物品摞在a物品之上时一定是把b物品的重心放到a物品的边沿上
好比把a物品当成桌子一定是放到桌沿上
再将a和b看成同一个物品时一定是放到下一个物品的边沿上 一旦一个物体的质量和重心的位置确定了这个物品的其他属性就无关紧要了从而无后效性
所以状压每次往下垫的书是哪一本确定放的顺序关注的是伸出去的最大值 往下垫的书的重心位于l/2处质量为a
上面的书看成一体时重心位于边沿质量为b
那么新的重心根据杠杆原理位于距边沿a/(ab)的位置记adda/(ab) 记原来的伸出去的最大值为x则新的最大值为xadd
此外可以旋转一下整个物体使整个物体的重心仍落在边沿上不落下去
但是伸出边沿的是往下垫的书的另外半边也就是l-add这半边二者取max即可 所以如果最优解是第i本书伸的最远最上面的书是1最下面的书是n
一定是对于j∈[1,i-1]来说把[1,j]看成一体时[1,j]的重心压在j1的左边沿
对于j∈[i1,n]来说将[1,j-1]看成一体时[1,j-1]的重心压在j的右边沿
每次枚举的时候旋转or不旋转二选一都试一下显然可以覆盖这种情况
代码1
维护的是长度l、到左边沿的距离p、整体的质量w
// Problem: Rikka with Book
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/9328/J?headNavacm
// Memory Limit: 1048576 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includebits/stdc.h
using namespace std;
#define rep(i,a,b) for(int i(a);i(b);i)
#define per(i,a,b) for(int i(a);i(b);--i)
typedef long long ll;
typedef double db;
typedef pairll,int P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr(#x):x ;
#define dbg2(x) cerr(#x):xendl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf(%d,(a))
#define scll(a) scanf(%lld,(a))
#define pt(a) printf(%d,a);
#define pte(a) printf(%d\n,a)
#define ptlle(a) printf(%lld\n,a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N20,M(120)5;
int n;
db dp[M];
int lb(int x){return x(-x);
}
struct node{db l,p;//长度 离左侧距离int w;//质量node(){l0;p1e7;w0;}db dis(){return l-p;}void show(int i-1){printf(i:%d l:%lf p:%lf w:%d\n,i,l,p,w);}
}e[M];
//b放在a上
bool operator(node a,node b){return a.dis()b.dis();
}
node mer(node a,node b){db xa.l-a.p;node c;db Ba.w*x/(a.wb.w);if(b.pa.l){//b更左c.lb.l;c.pb.p-B;//b.l-b.pB}else{//a更左c.la.lb.l-b.p;c.pa.l-B;//b.l-b.pB}c.wa.wb.w;if(c.pc.l-c.p)c.pc.l-c.p;//puts();//a.show();b.show();c.show();//puts();return c;
}
void sol(){sci(n);rep(i,0,n-1){int x1i;scanf(%lf,e[x].l);e[x].pe[x].l/2.0;}rep(i,0,n-1){int x1i;scanf(%d,e[x].w);}int up(1n)-1;rep(i,1,up){if(lb(i)i)continue;//printf(i:%d\n,i);rep(j,0,n-1){if(!(ij1))continue;int v1j,othi^v;node wmer(e[v],e[oth]);//只枚举最底下那个是什么if(we[i])e[i]w;//e[oth].pe[oth].l-e[oth].p;//wmer(e[v],e[oth]);//if(we[i])e[i]w;//w.show();}//if(e[i].pe[i].l-e[i].p)e[i].pe[i].l-e[i].p;//b[1].pb[1].l-b[1].p;//e[i].show(i);}printf(%.10lf\n,e[up].dis());
}
int main(){sol();return 0;
}
代码2三个顶俩代码
发现无需维护长度l和距一端的位置p只维护右半边伸出去的最大值即可
每次尝试一下翻或不翻
#include bits/stdc.husing namespace std;
int n,l[30],w[30],x[1100000];
double f[1100000];int main()
{int i,j;scanf(%d,n);for(i0;in;i)scanf(%d,l[i]);for(i0;in;i)scanf(%d,w[i]);for(i1;i(1n);i){for(j0;jn;j)if(i(1j))break;x[i]x[i-(1j)]w[j];}for(i1;i(1n);i){for(j0;jn;j)if(i(1j))f[i]max(f[i],max(f[i^(1j)]double(0.5*w[j]*l[j])/x[i],l[j]-double(0.5*w[j]*l[j])/x[i]));}printf(%.12lf\n,f[(1n)-1]);return 0;
}
