Home » 国际竞赛 » Details

USACO 2019 December Contest, Platinum Problem 1. Greedy Pie Eaters

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月1日下午3:40

USACO 2019 December Contest, Platinum Problem 1. Greedy Pie Eaters

armer John has $M$ cows, conveniently labeled $1 \dots M$ , who enjoy the occasional change of pace from eating grass. As a treat for the cows, Farmer John has baked $N$ pies ( $1 \leq N \leq 300$ ), labeled $1 \dots N$ . Cow $i$ enjoys pies with labels in the range $[l_{i}, r_{i}]$ (from $l_{i}$ to $r_{i}$ inclusive), and no two cows enjoy the exact same range of pies. Cow $i$ also has a weight, $w_{i}$ , which is an integer in the range $1 \dots 10^{6}$ .

Farmer John may choose a sequence of cows $c_{1}, c_{2}, \dots, c_{K},$ after which the selected cows will take turns eating in that order. Unfortunately, the cows don't know how to share! When it is cow $c_{i}$ 's turn to eat, she will consume all of the pies that she enjoys --- that is, all remaining pies in the interval $[l_{c_{i}}, r_{c_{i}}]$ . Farmer John would like to avoid the awkward situation occurring when it is a cows turn to eat but all of the pies she enjoys have already been consumed. Therefore, he wants you to compute the largest possible total weight ( $w_{c_{1}} + w_{c_{2}} + \dots + w_{c_{K}}$ ) of a sequence $c_{1}, c_{2}, \dots, c_{K}$ for which each cow in the sequence eats at least one pie.

SCORING:

Test cases 2-5 satisfy $N \leq 50$ and $M \leq 20$ .
Test cases 6-9 satisfy $N \leq 50.$

INPUT FORMAT (file pieaters.in):

The first line contains two integers $N$ and $M$ $(1 \leq M \leq \frac{N (N + 1)}{2})$ .The next $M$ lines each describe a cow in terms of the integers $w_{i}, l_{i}$ , and $r_{i}$ .

OUTPUT FORMAT (file pieaters.out):

Print the maximum possible total weight of a valid sequence.

SAMPLE INPUT:

2 2
100 1 2
100 1 1

SAMPLE OUTPUT:

In this example, if cow 1 eats first, then there will be nothing left for cow 2 to eat. However, if cow 2 eats first, then cow 1 will be satisfied by eating the second pie only.

Problem credits: Benjamin Qi

<h3>USACO 2019 December Contest, Platinum Problem 1. Greedy Pie Eaters 题解(翰林国际教育提供，仅供参考)</h3>
<p style="text-align: center;">题解请<a href="/register" target="_blank" rel="noopener">注册</a>或<a href="/login" target="_blank" rel="noopener">登录</a>查看</p>
[/hide]

(Analysis by Benjamin Qi)

Subtask 1:

We can use bitmask DP and construct the sequence in order. Let $c u r$ be the bitmask representing the cows which have already been chosen and let $r e s [c u r]$ be the maximum possible length of the sequence for this state. Furthermore, let $m a s k [c u r]$ be the bitmask representing the pies that are chosen by these cows and $t o t [i]$ be the bitmask representing the pies which cow $i$ enjoys. Then we can only add cow $i$ to the sequence if $m a s k [c u r] \neq (m a s k [c u r] & t o t [i])$ .

It's easy to implement a solution that runs in $O (M 2^{M})$ time.

Subtask 2:

Any reasonable solution which is polynomial in $N$ should pass.

Subtask 3:

We can solve this problem in $O (N^{3}) .$ Let $d p [l] [r]$ denote the maximum number of cows such that the set of eaten pies is a subset of the range $l \dots r .$ Then we can write

d p [l] [r] := max l \leq i < r (d p [l] [i] + d p [i + 1] [r]) .

Furthermore, suppose that the last cow in the sequence ate pie $i$ for some $l \leq i \leq r .$ Then if there exists an interval $[a, b]$ such that $l \leq a \leq i \leq b \leq r,$ we can write

d p [l] [r] := max (d p [l] [r], d p [l] [i - 1] + d p [i + 1] [r] + m x [i] [l] [r]),

where $m x [i] [l] [r]$ is the maximum weight over all cows $[l_{i}, r_{i}]$ satisfying $l \leq l_{i} \leq i \leq r_{i} \leq r .$ Our answer will be the value of $d p [0] [N - 1] .$

This DP can be computed in $O (N^{3})$ time.

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

typedef long long ll;
typedef vector<int> vi; 
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
 
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; }
	
void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}

const int MX = 300;
 
int N,M,dp[MX][MX];
int mx[MX][MX][MX];
vi w,l,r;
 
int main() {
	setIO("pieaters"); 
	cin >> N >> M;
	w.rsz(M); l.rsz(M), r.rsz(M);
	F0R(i,M) {
		cin >> w[i] >> l[i] >> r[i]; 
		l[i] --,r[i] --;
		FOR(j,l[i],r[i]+1) 
			ckmax(mx[j][l[i]][r[i]],w[i]);
	}
	F0R(i,N) {
		R0F(j,i+1) FOR(k,i,N) {
			if (j) ckmax(mx[i][j-1][k],mx[i][j][k]);
			if (k < N-1) ckmax(mx[i][j][k+1],mx[i][j][k]);
		}
	}
	R0F(a,N) FOR(b,a,N) {
		FOR(c,a,b) ckmax(dp[a][b],dp[a][c]+dp[c+1][b]);
		FOR(c,a,b+1) if (mx[c][a][b]) { // among all those covering c >= a
			int res = mx[c][a][b];
			if (c > a) res += dp[a][c-1];
			if (c < b) res += dp[c+1][b];
			ckmax(dp[a][b],res);
		}
	}
	cout << dp[0][N-1] << "\n";
}

[/hide]