题意
给你n个货币价格，然后通过调整一些货币的大小，使得所有比自己小的货币都是该货币的约数，调整前第 i 货币为a，调整后为b 那么变化率为 ri=|a-b|/a ，总变化率为max（ri）。求最小的总变化率。
分析
DP
状态转移方程 dp[i][k]=min(max(dp[i-1][j], |k-a[i]|/a[i]));
dp[i][k]表示前i个货币调整后，第i个货币为k时，最大的变化率是多少。
因为每个货币都是前面货币的倍数，所以只要它是前一个货币的倍数即可。
我们枚举前一个货币的范围和这个货币的范围，前一个货币范围就是1到2*a[i-1]-1，因为变化率如果为1，那肯定不如把所有货币置为1，总变化率更小。而当前货币的范围就是前一个货币的1倍、2倍、... 小于2*a[i]-1。
初始化时，dp[i][j]=1，最大变化率肯定小于1。
最后答案就是max(dp[n][i])了。
要注意的是，开dp数组时要开到200005，因为变化后的最大值接近原来的两倍。
这题网友的方法是二分 dfs搜索，dp是学长给的题解里的方法。
代码
代码语言：javascript复制#include<stdio.h>
#include<algorithm>
#include<cmath>
#define F(a,b,c) for(int a=b;a<=c;a =b)
using namespace std;
int n,a[21]={1};
double dp[21][200005],ans=1;
int main(){
scanf("%d",&n);
F(i,1,n) scanf("%d",&a[i]);
F(i,1,n) F(j,1,200001) dp[i][j]=1;
F(i,1,n)
F(j,1,2*a[i-1]-1)
F(k,j,2*a[i]-1)//每次 j
dp[i][k]=min(dp[i][k],max(dp[i-1][j],fabs(k-a[i])/a[i]));
F(i,1,2*a[n]-1)
if(ans>dp[n][i])ans=dp[n][i];
printf("%.12lfn",ans);
return 0;
} 
