BestCoder Round #39 1002

时间：2015-05-01 15:57:04 收藏：0 阅读：196

Hint

F(1)=2 F(2)=0 F(3)=4 F(4)=0

---------------------------------------------------------------------华丽的分割线-------------------------------------------------------------------

维护一个vis数组 vis[i]记录i上一次出现的位置，从右往左遍历给出的数字，每个数字num都从vis[num * 2]从左往右暴力vis数组

时间复杂度为

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn = 10050;
 6 int num[maxn]; int vis[maxn];
 7 int main()
 8 {
 9     int n;
10     while(scanf("%d", &n) == 1) {
11         int maxnum = 0;
12         for(int i = 0 ; i < n  ; i++) scanf("%d", &num[i]), maxnum = max(maxnum, num[i]);
13         memset(vis, 0, sizeof(vis));
14         int ans = 0;
15         for(int i = n - 1 ; i >= 0 ;i--) {
16             vis[num[i]] = i + 1; int id = 0x3f3f3f3f;
17             for(int j = num[i] * 2 ; j  <= maxnum ; j += num[i]) {
18                 if(vis[j])
19                     id = min(id, vis[j]);
20             }
21             if(id != 0x3f3f3f3f) ans += id;
22             ///printf("%d\n", ans);
23         }
24         printf("%d\n", ans);
25     }
26     return 0;
27 }

原文：http://www.cnblogs.com/tooyoungtoosimple/p/4470777.html