[关闭]
@zzzc18 2017-09-28T07:38:20.000000Z 字数 1085 阅读 1133

Code-Festival-2017-qualA_____F - Squeezing Slimes

AtCoder


已知一个若干个1构成的序列,然后每次可以选择2n个连续的数,按照(1,2)(3,4),...(2n-1,2n)的方式合并,得到最终的序列。现在告诉你最终的序列,求最少几步。


官方题解说构造三元组,然后证明了其一定是最优的
然后DP解决
editorial(1).pdf297.3kB

感觉非人类


感觉这个说的还靠谱一些

显然应该倒过来做。那么考虑一次操作就是把连续的若干>1的数拆成两半,显然应该贪心地拆成均匀的两份。

再考虑题解里DP的过程,确实均分才是最少的构造步数

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. typedef long long LL;
  6. const LL MAXN = 200000+9;
  7. LL n;
  8. LL a[MAXN];
  9. struct DATA{
  10. LL k,pd;
  11. }num[MAXN];
  12. LL dp[MAXN][2];
  13. LL ans;
  14. DATA cal(LL x){
  15. LL i;LL pos;
  16. for(i=1,pos=0;i<=x;i<<=1,pos++);
  17. i>>=1;
  18. if(i==x){
  19. return (DATA){pos-1,0};
  20. }
  21. else{
  22. return (DATA){pos,1};
  23. }
  24. }
  25. void solve(){
  26. LL i;
  27. for(i=1;i<=n;i++){
  28. num[i]=cal(a[i]);
  29. }
  30. for(i=1;i<=n;i++)
  31. ans+=num[i].k;
  32. for(i=2;i<=n;i++){
  33. dp[i][0]=max(dp[i][0],dp[i-1][0]+min(num[i-1].k-num[i-1].pd,num[i].k));
  34. dp[i][0]=max(dp[i][0],dp[i-1][1]+min(num[i-1].k,num[i].k));
  35. dp[i][1]=max(dp[i][1],dp[i-1][0]+min(num[i-1].k-num[i-1].pd,num[i].k-num[i].pd));
  36. dp[i][1]=max(dp[i][1],dp[i-1][1]+min(num[i-1].k,num[i].k-num[i].pd));
  37. }
  38. printf("%lld\n",ans-max(dp[n][0],dp[n][1]));
  39. }
  40. int main(){
  41. scanf("%lld",&n);
  42. LL i;
  43. for(i=1;i<=n;i++)
  44. scanf("%lld",&a[i]);
  45. solve();
  46. return 0;
  47. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注