SRM 594 950pt

给定n, w, x(n ≤ 3000)表示把n个物品放进宽为w的矩形内。其中第i号物品放在第(i – 1) / w行，第(i – 1) % w列上。每次能圈取一个平行坐标轴的矩形把里面的物品全部删除掉。删除以后，对应的物品会往前往上凑上空掉的位置。问至少要多少次操作可以使得最后只剩第x号物品。

这题其实有三个point，都发现了就好做了。

1. 答案最多是4。做法是先删掉所有行号小于x的物品，然后x被放到第一行了。接着删掉所有行号大于第一行的。最后删除一左一右即可。
2. 离达到目标只剩一步的时候，是可以O(1)判断出来的。
3. 对于同样的x和w，随着n的递减，答案不增。

比赛的时候想到第一条和第二条，但是第三条没有注意到。
有了第一条，那么只需要能判断3次以内能不能做到即可。再根据第二条，只要能枚举两步的行为，问题就能够得到顺利解决。
本来一个r*c＝n的矩形里，子矩形的数目是$$r^2 * c^2 \leq n^2$$级别的。但是由于第三点，分x的上下左右分别考虑的时候，会发现都可以少掉一维r和一维c。于是枚举一次操作的复杂度就是O(r*c=n)的了。这样就足够pass这道题目。

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int w, ans;

bool isOne(int n, int x) {
	if (x % w == 0 && x + 1 == n)
		return 1;
	else if (w == 1 && !x)
		return 1;
	else if (n <= w && x + 1 == n)
		return 1;
	else if (n <= w && !x)
		return 1;
	else if (n < 2 * w && x + 1 == w && !(x / w))
		return 1;
	else
		return 0;
}

void solve(int n, int x, int cur) {
	if (n == 1) {
		ans = cur;
		return;
	}
	if (isOne(n, x)) {
		ans = cur + 1;
		return;
	}
	if (cur + 2 >= ans) return;
	int r = (n - 1) / w + 1;
	int c = w;
	int xr = x / w;
	int xc = x % w;
	for (int i = 1; i <= xr; i++)
		for (int j = 1; j <= w; j++)
			solve(n - i * j, x - i * j, cur + 1);
	if (xr + 1 != r) solve(c * (xr + 1), x, cur + 1);
	for (int i = 0; i <= xr; i++) {
		for (int j = 1; j <= xc; j++) {
			int d = (r - xr) * j + i * j - max(0, j - 1 - (n - 1) % w);
			solve(n - d, x - (i + 1) * j, cur + 1);
		}
	}
	for (int i = 0; i <= xr; i++) {
		for (int j = 1; j <= w - xc - 1; j++) {
			int d = (r - xr) * j - max(0, min(xc + j - (n - 1) % w, j));
			d += i * j;
			solve(n - d, x - i * j, cur + 1);
		}
	}
}

int gao(int n, int w, int x) {
	::w = w;
	x--;
	ans = 4;
	solve(n, x, 0);
	return ans;
}

class FoxAndAvatar {
public:
	int minimalSteps(int, int, int);
};

int FoxAndAvatar::minimalSteps(int n, int width, int x) {
	return gao(n, width, x);
}