题解：P5948 [POI2003] Chocolate

一眼贪心，为什么呢？

从题面中我们可以看见纵向切一刀横向就多一刀的代价，所以我们把所有代价混一起排序从大到小切割即可。

（结尾附证明）

注：要开 long long，最坏情况约为：，肯定炸 。

代码如下：

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n, m;
struct Choco
{
    int x;
	int flag;
} a[20005];
int cnt[2];
bool cmp(Choco a, Choco b)
{
	return a.x > b.x;
}
ll ans;

int main()
{
    cin >> n >> m;
	n--, m--;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i].x;
        a[i].flag = 0;
    }
	for (int i = 1; i <= m; i++)
    {
		cin >> a[i + n].x;
		a[i + n].flag = 1;
	}
	sort(a + 1, a + n + m + 1, cmp);
	for (int i = 1; i <= n + m; i++)
    {
		ans += a[i].x * (cnt[!(a[i].flag)] + 1); 
		cnt[a[i].flag]++;
	}
	cout << ans << "\n";
    return 0;
}

---

附：证明

通过题面我们可以看出，如果我们纵向切了 刀，此时想去切横向就要增加 的代价而不是 的代价。

推导出：对于切一次的代价，下一次以不同方向切的必然会增加一倍的代价。

所以我们最好的解决方法就是将代价从大到小排序来避免较大的代价变得更大。

以此，证明结束。