CF254E Dormitory 题解

发表于 分类于

本文迁移自洛谷原文。

题目大意：

有 $n$ 天，第 $i$ 天你会收到 $a_i$ 份食物。食物有保质期，第 $i$ 天收到的食物只能在第 $i$ 天和第 $i+1$ 天食用。

你还有 $m$ 个朋友。第 $i$ 个朋友会在第 $l_i$ 至 $r_i$ 天拜访你，食量是 $c_i$ 份食物。

你每天可以选择一些朋友供应食物（必须供给正好 $c_i$ 份食物，一个朋友一天只能供给一次），每贡献一人次你的人气值就会 $+1$。

同时，你每天必须吃 $v$ 份食物。

问你 $n$ 天后你的人气值最大是多少。

题解：

令 $dp_{i,j}$ 表示考虑到第 $i$ 天，昨天剩下了 $j$ 份食物时你最大的人气值。

转移：

很显然，我们每一天肯定会先吃昨天的剩饭，不够了再吃今天的饭。

然后选择朋友的话，我们可以贪心的选：按照朋友的饭量从小到大排序，选最小的前 $k$ 个。

具体可以参考代码

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
const int mxn=444;
int n,v,m;
int a[mxn];
vector<pair<int,int> >c[mxn];
int dp[mxn][mxn*2],pre[mxn][mxn*2],preg[mxn][mxn*2]; //pre[][]记录剩饭由哪儿转移过来，preg记录了当天请了饭量前多少小的朋友吃饭
inline void solve(){
	cin>>n>>v;
	for(int i=1;i<=n;++i)cin>>a[i];
	cin>>m;
	for(int i=1;i<=m;++i){
		int l,r,t;cin>>l>>r>>t;
		for(int j=l;j<=r;++j)c[j].push_back(mp(t,i));
	}
	for(int i=1;i<=n;++i)sort(c[i].begin(),c[i].end());
	for(int i=0;i<mxn;++i)for(int j=0;j<mxn*2;++j)dp[i][j]=-1145141;
	dp[1][0]=0;
	for(int i=1;i<=n;++i){
		for(int j=0;j<=800;++j){//dp[i][j]表示考虑到第i天，昨天剩下了j的食物所能得到的最大值
			if(dp[i][j]<0)continue;
			int yes=j,tod=a[i];    //分别代表昨天的剩饭和今天新增的饭
			if(yes>=v)yes-=v;
			else tod-=(v-yes),yes=0;  //先处理今天自己吃的饭
			int x=tod+yes;
			if(dp[i][j]>dp[i+1][tod]){
				dp[i+1][tod]=dp[i][j];
				pre[i+1][tod]=j;
				preg[i+1][tod]=0;
			}
			int sum=0;
			for(int k=0;k<c[i].size();++k){
				sum+=c[i][k].first;
				if(sum>x)break;
				int rem=min(tod,x-sum);  //还是先吃剩饭，然后处理昨天不能保留到明天的饭
				if(dp[i][j]+k+1>dp[i+1][rem]){
					dp[i+1][rem]=dp[i][j]+k+1;
					pre[i+1][rem]=j;
					preg[i+1][rem]=k+1;
				}
			}
		}
	}
	int pos=0;
	for(int i=1;i<=800;++i)if(dp[n+1][i]>dp[n+1][pos])pos=i;
	cout<<dp[n+1][pos]<<'\n';
	vector<int>bk;
	bk.clear();
	int lst=pos;
	for(int i=n+1;i>1;--i){
		bk.push_back(preg[i][lst]);
		lst=pre[i][lst];
	}
	for(int i=bk.size()-1;~i;--i){
		cout<<bk[i]<<' ';
		for(int j=0;j<bk[i];++j)cout<<c[bk.size()-i][j].second<<' ';
		cout<<'\n';
	}
}
int main(){
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;
	//cin>>T;
	for(;T--;)solve();
	return 0;
}