紫书习题 8-22 UVa 1622 （构造法）

这道题的构造法真的复杂……要推一堆公式……这道题写了几天了……还是没写出来……

一开始简单的觉得先左右来回，然后上下来回，然后把剩下的执行完了好了，然后就WA。

然后换了个思路，觉得是贪心，觉得只要保证当前留下的最多就ok了，然后又WA。

这里不能每一步贪心，因为当前最优不能保证以后是最优的。

然后找数据发现，其实当留下的个数一样多的时候还要有格外的优先级，而且分很多种情况。

然后就去看了很多博客。

发现原来开始还要先判断往南北还是东西，然后东西完了之后再每次判断南北还是西，然后再判断

剩下的。想的这么周全也是人才。

#include<cstdio>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

typedef long long ll;

ll solve(ll x, ll y, ll n, ll s, ll w, ll e)

{

	ll res = 0;

	if(s > n) swap(s, n);

	if(e > w) swap(e, w);

	if(n)   //东西来回

	{

		res += x * y;

		x--; n -= s;

		if(n) res += x * y * s * 2, n--;

		else res += x * y * (s * 2 - 1);

		s = 0;

	}

	if(w)  //判断向南北还是向西

	{

		w -= e;

		if(w) e *= 2, w--;

		else e = e * 2 - 1;

		while((1 - y) * e >= y - x && n) //两串很长的公式最后的化简结果

		{

			res += x * y;

			n--; x--;

		}

		res += x * y; y--;

		res += x * y * e; e = 0;

	}

	while(x * y > 0 && n + w > 0)  //剩下的处理掉

	{

		res += x * y;

		if((x > y && n) || !w) n--, x--;

		else w--, y--;

	}

	return res;

}

int main()

{

	int kase = 0;

	ll x, y, n, s, w, e; //要开long long

	while(~scanf("%lld%lld", &x, &y) && x && y)

	{

		scanf("%lld%lld%lld%lld", &n, &s, &w, &e);

		ll res = max(solve(x, y, n, s, w, e), solve(y, x, e, w, n, s)); //两种情况都做一遍取最大

		printf("Case %d: %lld\n", ++kase, res);

	}

	return 0;

}

巴特西

紫书习题 8-22 UVa 1622 （构造法）

最新文章

热门文章

巴特西

紫书 习题 8-22 UVa 1622 （构造法）

最新文章

热门文章

紫书习题 8-22 UVa 1622 （构造法）