n次贪心
本题一次贪心的话有可能答案错误,但总共只有n<=10个数,可以以每一个数为起点都贪心一次,然后取最小值,时间复杂度依然很低,这样代码能过掉,不过我也没有严谨的证明,如果有人能找到反例的话也可以发一下,然后呼叫y总加强数据0.0
贪心思路比较简单,循环每一个数看看能放到哪个组里,如果都不能就开新组
C++ 代码
#include <iostream>
#include <vector>
using namespace std;
const int N=15;
vector<int> v[N];
int a[N];
bool e;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
int cnt=1;
int res=10;
for(int t=1;t<=n;t++)
{
for(int i=1;i<=10;i++)
v[i].clear();
v[1].push_back(a[t]);
cnt=1;
e=false;
for(int i=(t+1)%n?(t+1)%n:n,c=1;c<n;i=(i+1)%n?(i+1)%n:n,c++)
{
for(int j=1;j<=cnt;j++)
{
e=false;
for(int k=0;k<v[j].size();k++)
if(gcd(v[j][k],a[i])>1) {e=true;break;}
if(!e)
{
v[j].push_back(a[i]);
break;
}
}
if(e)
{
cnt++;
v[cnt].push_back(a[i]);
}
}
res=min(res,cnt);
}
cout<<res;
}