高分求解一道C语言的有难度的题目

来源：百度知道 编辑：UC知道 时间：2024/05/28 23:14:52
有n(1<=n<=20000)头猪，他们围成了一个圈。猪是要染色的，其中第i头猪身上要染ai种颜色(1<=ai<=100000)。但是这个圈内相邻的两头猪（也就是任意猪的左边和右边）身上不能有相同的颜色。
求出要把所有猪按要求染色，至少需要多少种颜色。

输入：
第一行n(1<=n<=20000)
第二行开始每行有一个数ai(1<=ai<=100000)表示第i个猪要在身上涂ai种颜色

输出最少需要的颜色数量
时间限制1秒，内存限制64M
（也就是任意猪的左边和右边）
这中间猪的左右2猪位置不相邻，可以同色。但中间的猪和左边不能同，和右边也不能同

那个tanyuguo的求数列bi最大值的算法不对
10个黑盒数据才对了3个。

不好意思，分奇偶的算法也用了，才过了1个。
代码如下
int a[100001],b[100001],n;
int main()
{
int i,j;
scanf("%d\n",&n);
for(i=1;i<=n;i++)
scanf("%d\n",&a[i]);
if(n==1)
{
printf("%d\n",a[1]);
return 0;
}
if(n%2==0)
{
for(i=2;i<=n;i++)
b[i]=a[i]+a[i-1];
b[1]=a[1]+a[n];
for(i=1,j=0;i<=n;i++)
if(b[i]>j)
j=b[i];
}
else
{
for(i=2;i<n;i++)
b[i]=a[i]+a[i-1]+a[i+1];
b[1]=a[1]+a[n]+a

原数列是a(1),a(2),...,a(n)
令数列b的各项
b(i)=a(i)+a(i+1) 1<=i<=n-1;
b(n)=a(n)+a(1)
我认为这题就是求数列bi的最大值

给500分我帮你编，我大一学的本人是计算机专业的

看错题目了

ai是什么哇？

tanyuguo 思路是对的

但是当猪个数为奇数时会有点问题，假设有3头猪ABC ， 每头要染两种颜色
A 颜色 1，2
B 颜色 3，4
C这时是不能用回1，2的，因为C和A也是相邻
C只能取新的两种颜色 5，6

所以要分奇偶来计算
当猪个数为偶数时 tanyuguo 的 算法
当猪个数为奇数时 找相邻3个猪颜色的和的最小值

--------------------------------------------

以上的确有问题。。。。。确切的说应该是

当猪个数为偶数时 tanyuguo 的 算法
当猪个数为奇数时 找出相邻3个猪颜色的和的最小值，再和相邻两猪颜色和的最小值相比较，取其中大者。

----------------
int a[100001],b[100001],n;
int main()
{
int i,j,k;
scanf("%d\n",&n);
for(i=1;i<=n;i++)
scanf("%d\n",&a[i]);
if(n==1)
{
printf("%d\n",a[1]);
return 0;
}

for(i=2;i<=n;i++)
b[i]=a[i]+a[i-1];
b[1]=a[1]+a[n];
for(i=1,j=b[1];i<=n;i++)
if(b[i]<j)
j=b[i];