标签：rw return 删除 Ploughing int res POI2006ORK define

POI #Year2006 #贪心 #暴力

如果将所有的列干掉，那么贪心的如果可以删除一列就优先删除一列

当左右列不可以删除时，考虑上下行先删除谁不好判断

考虑在操作之前先枚举上面删除多少行，这样在操作时就可以贪心的使得下面删掉的行尽可能少

也就是贪心先删除上面

// Author: xiaruize
#ifndef ONLINE_JUDGE
#define debug(...) std::cerr << __LINE__ << ": [", __DEBUG_UTIL__::printer(#__VA_ARGS__, __VA_ARGS__)
#define debugArr(...) std::cerr << __LINE__ << ": [", __DEBUG_UTIL__::printerArr(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...)
#define debugArr(...)
#endif
using namespace std;
#ifndef ONLINE_JUDGE
clock_t start_clock = clock();
#endif
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)

{
	if (a > b)
		return a;
	return b;
}
int min(int a, int b)
{
	if (a < b)
		return a;
	return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e3 + 10;

int k, n, m;
int a[N][N], b[N][N];
int rw[N][N], col[N][N];

int calc1(int x)
{
	int u = 1, d = n;
	int res = 0;
	for (int l = 1, r = m; l <= r;)
	{
		while (l <= r && col[d][l] - col[u - 1][l] <= k)
			l++;
		while (l <= r && col[d][r] - col[u - 1][r] <= k)
			r--;
		// debug(x, l, r, sum[d][r] - sum[u - 1][r]);
		if (l > r)
			break;
		if (u < x && rw[u][r] - rw[u][l - 1] <= k)
		{
			u++;
			res++;
		}
		else if (u <= d && rw[d][r] - rw[d][l - 1] <= k)
		{
			res++;
			d--;
		}
		else
			return INF;
	}
	return res + m;
}

void solve()
{
	cin >> k >> m >> n;
	rep(i, 1, n)
	{
		rep(j, 1, m)
		{
			cin >> a[i][j];
			b[j][i] = a[i][j];
			rw[i][j] = a[i][j] + rw[i][j - 1];
			col[i][j] = a[i][j] + col[i - 1][j];
			// debug(sum[i][j]);
		}
	}
	int res = INF;
	rep(i, 1, n) res = min(res, calc1(i));
	// cerr << res << endl;
	swap(n, m);
	mms(a, 0);
	mms(rw, 0);
	mms(col, 0);
	rep(i, 1, n)
	{
		rep(j, 1, m)
		{
			a[i][j] = b[i][j];
			rw[i][j] = a[i][j] + rw[i][j - 1];
			col[i][j] = a[i][j] + col[i - 1][j];
			// debug(sum[i][j]);
		}
	}
	rep(i, 1, n) res = min(res, calc1(i));
	cout << res << endl;
}

#ifndef ONLINE_JUDGE
bool end_of_memory_use;
#endif

signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int testcase = 1;
	// cin >> testcase;
	while (testcase--)
		solve();
#ifndef ONLINE_JUDGE
	cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
	cerr << "Time use:" << (double)clock() / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
	return 0;
}

标签：rw,return,删除,Ploughing,int,res,POI2006ORK,define
From： https://www.cnblogs.com/xiaruize/p/18136789