一个圆上有等距的n个顶点,有一些顶点不能选,问是否选取若干点组成一个正多边形.
假设可以构成一个正d多边形 ,首先需要d|n,其次需要有dd个点使得相邻两点距离均为n/d个点
枚举n的因子d,以dp[i]表示以i结尾最多可以有几个连续的距离均为d的点,进而有转移方程
转移方程:dp[i] = a[i] + dp[i - n/d] (i - n/d > 0)
时间复杂度O(nsqrt(n))
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6; int a[maxn], dp[maxn]; int n; int find(int d) { if (x <= 2) return 0; for (int i = 1; i <= n; i++) { dp[i] = a[i] + dp[max(i - n / d, 0)]; if (dp[i] >= d) return 1; } return 0; } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i * i <= n; i++) { if (n % i == 0) { int f1 = find(i); int f2 = find(n / i); if (f1 || f2) { cout << "YES" << endl; return 0; } } } cout << "NO" << endl; return 0; }