题目链接:https://ac.nowcoder.com/acm/contest/13168/G
这篇博客重点在一维优化代码的初始化操作.
题目要求:给n份论文,每份有k的可能性通过,有一种独特的方法来评估论文提交的成功。他们使用的研究生产力指数,定义为a^(a/s)其中s是提交的文件总数,a是会议接受的文件数量.
例如:如果提交一个文件并被接受,索引是1^(1/1)=1;
如果提交了10篇论文,并接受了3篇论文,索引3^(3/10)≈1.390389.
有N个论文 如果明智地选择提交哪些论文,她的研究生产力指数的最大预期值是什么.
一个比较常规的概率DP,比赛时题目没搞清楚,思路有点偏,就放弃了,去做别的题目.
二维
dp[i][j]=dp[i-1][j](1-a[i]/100.0)+dp[i-1][j-1]a[i]/100.0;
dp[i][j]表示第i件物品中过了j件物品的概率.如果第i件过了,那么就是dp[i-1][j-1]a[i]的概率,如果第i件没过就是dp[i-1][j](1-a[i])的概率.
二维DP double dp[105][105]; int a[105]; bool cmp(int x,int y) { return x>y; } int main() { int n; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } sort(a+1,a+1+n,cmp); dp[0][0]=1; for(int i=1;i<=n;i++) { dp[i][0]=dp[i-1][0]*(1-a[i]/100.0); } for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) dp[i][j]=dp[i-1][j]*(1-a[i]/100.0)+dp[i-1][j-1]*a[i]/100.0; double ans=0; double tem=0; for(int i=1;i<=n;i++) { tem=0; for(int j=1;j<=i;j++) { tem+=dp[i][j] * pow(j, j * 1.0 / i); } ans=max(ans,tem); } printf("%.9lf\n",ans); }
一维DP
一维思路
由于dp[i][j]=dp[i-1][j](1-a[i]/100.0)+dp[i-1][j-1]a[i]/100.0;
dp[i][j]是由dp[i][j-1]推导而来所以是逆序.
double dp[105]; double a[105]; bool cmp(double x,double y) { return x>y; } int main() { int n; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; a[i]=a[i]/100.0; } sort(a+1,a+1+n,cmp); dp[0]=1; double ans=0; for(int i=1;i<=n;i++)//提交数量 { double tem=0; for(int j=i;j>=1;j--)//通过数量. { dp[j]= dp[j-1]*a[i] + dp[j]*(1-a[i]); tem+=dp[j]*pow(j,j*1.0/i); } dp[0]=dp[0]*(1-a[i]); ans=max(ans,tem); } printf("%.9lf\n",ans); }