題意：同奇偶連線(xiàn)代價(jià)為a,不同奇偶連線(xiàn)代價(jià)為b,求n個(gè)點(diǎn)連線(xiàn)的最小代價(jià)【注意a和b可以<=0】

思路： 很明顯我們可以手繪出兩層

奇數(shù)： x x x x

偶數(shù)： x x x x x

開(kāi)始分類(lèi)討論【注意奇數(shù)或偶數(shù)的個(gè)數(shù)為0的情況，就必須只能同類(lèi)連線(xiàn)】：

1.若a<0,b<0：連的線(xiàn)越多越好 同類(lèi)兩兩連線(xiàn)，不同類(lèi)也兩兩連線(xiàn)

2.若a<0,b>=0 或 a>0,b<=0:同類(lèi)全都連線(xiàn)，不同奇偶類(lèi)間連一條線(xiàn)

3.若a>0,b>0:分類(lèi)如果a<b則同類(lèi)連線(xiàn)，不同類(lèi)連一根；若b<a，則不同類(lèi)之間連線(xiàn)

void solve()
{
	int n, a, b;
	cin >> n >> a >> b;
	int cnt1 = 0, cnt2 = 0;
	for (int i = 1; i <= n; i++)
	{
		int num;
		cin >> num;
		if (num % 2)
			cnt1++;
		else
			cnt2++;
	}
	int na = 0, nb = 0;
	if (a <= 0 && b <= 0)
	{
		na = cnt1 * (cnt1 - 1) / 2 + (cnt2) * (cnt2 - 1) / 2;
		nb = cnt1 * cnt2;
	}
	else if (a <= 0 && b > 0)
	{
		na = cnt1 * (cnt1 - 1) / 2 + cnt2 * (cnt2 - 1) / 2;
		if (cnt1 && cnt2)
			nb = 1;
	}
	else if (a > 0 && b <= 0)
	{
		if (cnt1 && cnt2)
			nb = cnt1 * cnt2, na = 0;
		else
			na = n - 1, nb = 0;
	}
	else if (a > 0 && b > 0)
	{
		if (cnt1 && cnt2)
		{
			if (a < b)
				nb = 1, na = n - 2;
			else
				nb = n - 1, na = 0;
		}
		else
		{
			nb = 0, na = n - 1;
		}
	}
	int ans = 0;
	ans = a * na + b * nb;
	cout << ans << endl;
}