project euler 122(阅读理解)

發表於 更新於 分類於 Disqus： 文章字數： 685 所需閱讀時間 ≈ 2 分鐘

题目

https://projecteuler.net/problem=122

Addition chain

理解

看起来是个描述很简洁的题目

但是 我以为能有什么 局部最优

所以想说 15=3x5,也就是做一次 变3的工作 再一次变5的工作

对于质数 = 1+它的分解

然而错了

想不出什么方法，翻了翻wiki找到了上面的Addition chain

说计算addition chains目前是一个 NP-complete 的问题

好像也并不能dp

于是考虑生成过程，写了一个树上爆搜。

也就是 每个节点的子节点 等于该节点和，该节点以及祖先节点的和

这样就是加法过程，每次新增的数都是最大的。 但是这种情况 其实没有考虑 A-B-C-D-(D+B)-(D+C) , 这样就不是最后一个增加？

这样算法，感觉是有bug的？

虽然这样的代码过了。

不过，我打出了 bfs的 元素个数，看得到仅仅200的数据。191， 已经下标达到了4053954。

然后 我对拍了一下数据，最小的一个不一致是23，需要6步，而我错误的dp是7步

7步: 1+1=2,2+2=4,4+1=5,5+5=10,10+1=11,11+11=22,22+1=23

6步: 1+1=2,2+2=4,4+1=5,5+4=9,9+9=18,18+5=23

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define t3 1000+10
#define t4 10000+10
#define t5 100000+10
#define t6 1000000+10
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n-1;i>=a;i--)
#define pb push_back
const double pi = acos(-1.0);

namespace X{
  ll r(){ll r;scanf("%lld",&r);return r;} // read
  void add(ll &v0,ll &v1){(v0+=v1%MOD)%=MOD;} // add with MOD
  ll mpow(ll v,ll mi){ll r = 1;while(mi){if(mi%2)(r*=v)%=MOD;(v*=v)%=MOD;mi>>=1;};return r;} // quick power with MOD
  ll mod(ll v){return (v%MOD+MOD)%MOD;} // output
  ll gcd(ll a,ll b){return b == 0?a:gcd(b,a%b);}
};

// 错误的方法 start
ll dp[210];
int p[210];

void wayWrong(){
  p[1] = 1;
  rep(i,2,20){
    if(!p[i]){
      for(int j = i*i;j<=200;j+=i){
        if(!p[j]){
          p[j]= i;
        }
      }
    }
  }
  rep(i,2,201){
    if(!p[i]){
      dp[i] = 1+dp[i-1];
    }else{
      dp[i] = dp[p[i]] + dp[i/p[i]];
    }
  }
}

// 错误的方法 end

struct Node{
  int dep = 0 ;
  int val = 0;
  Node * fa = NULL;
};

const int N = 10000000;

Node nodes[N+10];

int leftcnt = 200 - 1 ;
ll ans[210];

int main(){
  int st = 0;
  int rear = 1;
  nodes[0].val = 1;
  while(st < rear){
    Node * p = &nodes[st];
    while(p != NULL){
      int newval = p->val + nodes[st].val;
      if(newval <= 200){
        if(ans[newval] == 0){
          printf("%d[dep:%d][bfs idx:%d]\n",newval,nodes[st].dep,rear);
          ans[newval] = nodes[st].dep + 1;
          leftcnt--;
          if(leftcnt == 0){
            break;
          }
        }
        nodes[rear].fa = &nodes[st];
        nodes[rear].dep = nodes[st].dep+1;
        nodes[rear].val = newval;
        rear++;
        if(rear > N){
          printf("leftcnt:%d\n",leftcnt);
          rep(i,1,201){
            if(!ans[i]){
              printf("noans:%lld\n",i);
            }
          }
          return 0;
        }
      }
      p=p->fa;
    }
    st++;
    if(leftcnt == 0){
      break;
    }
  }
  ll count = 0;
  rep(i,1,201){
    count += ans[i];
    // printf("%lld:%lld\n",i,ans[i]);
  }
  printf("%lld\n",count);
  return 0;
}