Center Street

在哈乐冰的中央大街上有N个仓买，我们可以将其抽象为一条线段上有N个顶点，仓买在线段上是均匀分布的，也就是说1号仓买在顶点1这个位置，2号仓买在顶点2这个位置...N号仓买在N这个位置。刚开始这些仓买之间是互相不通的，为了交流，工程师们建了一些路，但是由于资金有限，并不能在两两之间建一条路，他们只能有选择的建一些路。如果两个仓买A,B满足A是B的倍数，则A,B之间可以通一条路,当然这些路是双向的，A可以到B，B可以到A

例如N=8的时候：

仓买1向所有其他仓买通一条路。

2号仓买向4,6,8号仓买通路。

3号仓买仅和6号仓买通路。

4号仓买仅和8号仓买通路。

众所周知，建路需要花费很大一笔钱，所以资本家们需要过路的人需要收取一定费用，如果仓买A,B之间通路，则过路费为元。

现在小M站在1号仓买上，他想得知他分别到达1,2,3...N号仓买的最小花费。虽然他可以直接从1号仓买到达其他仓买，但是可以通过中转的方式让花费更少。你能帮帮他吗？

1号到4号仓买，直接到达花费9。但是可以先到达2，再通过2到4的路到达，花费为

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll dp[500005]; int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) dp[i]=1e18; dp[1]=0; for(int i=1;i<=n;i++) for(int j=2*i;j<=n;j+=i) dp[j]=min(dp[j],dp[i]+1ll*(j-i)*(j-i)); for(int i=1;i<=n;i++) printf("%lld ",dp[i]); }

#include<bits/stdc++.h> #define ll long long using namespace std; ll dp[500005]; int main(){ int n; dp[1]=0; cin>>n; for(int i=2;i<=n;i++) dp[i]=1e18; for(int i=1;i<=n;i++) for(int j=i+i;j<=n;j+=i){ dp[j]=min(dp[j],dp[i]+1LL*(j-i)*(j-i)); } for(int i=1;i<=n;i++) cout<<dp[i]<<" "; return 0; }

详情