P6893 [ICPC2014 WF] Buffed Buffet

, , ,

Description

https://www.luogu.com.cn/problem/P6893

Solution

首先显然把离散和连续拆成两个问题，最后 $O(W)$ 合并求最小值即可。

对于离散的，有 $f_{i,j}=\min f_{i-1,j-kw}+F(k)$，$F(k)=kt_0+k(k-1)\Delta t$。

可以把 $F(k)$ 看成 $w(i-k+1,i)$。显然 $w$ 满足四边形不等式，包含的小于相交的。考虑把 $f$ 分成关于 $w$ 的同余系之后分治做决策单调性即可。复杂度 $O(nW\log W)$。似乎有斜率优化做法，但是分治更好写。

对于连续的，观察到二次函数是凸的，其实可以看成 $n$ 个凸函数做 $(\max,+)$ 卷积。考虑闵可夫斯基和的过程，把每个函数的导数画出来，每次拿最大的一段，算一下重量为 $j$ 的时候的面积。复杂度 $O(n\log n+W)$，瓶颈在排序。

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 10005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m;
int cnt1,cnt2;
struct node {
	int w,t,dt;
}d[maxn],c[maxn];
bool cmp(node x,node y) {return x.t>y.t;}
const int inf=1e16;
namespace solve1 {
	int n;
	int f[maxn],g[maxn],h[maxn];
	int id;
	int F(int i,int k) {
		if (k<0) return -inf;
		return k*d[i].t-(k*(k-1)/2)*d[i].dt;
	}
	void solve(int l,int r,int L,int R) {
		if (l>r||L>R) return ;
		int mid=l+r>>1,p=L,i;
		for (i=L;i<=R&&i<=mid;i++) 
			if (h[mid]<g[i]+F(id,mid-i)) h[mid]=g[i]+F(id,mid-i),p=i;
		solve(l,mid-1,L,p);
		solve(mid+1,r,p,R); 
	}
	void main(void) {
		n=cnt1;
		int i,j,k,cnt;
		for (i=1;i<=m;i++) f[i]=g[i]=-inf;
		for (i=1;i<=n;i++) {
			int w=d[i].w;id=i;
			for (k=0;k<w;k++) {
				cnt=0;
				for (j=k;j<=m;j+=w) ++cnt,g[cnt]=f[j],h[cnt]=-inf;//g[0]=-inf;
				solve(1,cnt,1,cnt);
				for (j=k;j<=m;j+=w) f[j]=h[(j-k)/w+1];
			}
		}
	}
}
namespace solve2 {
	int n;
	double f[maxn];
	void main(void) {
		n=cnt2;
		int i,j=0;
		sort(c+1,c+1+n,cmp);
		for (i=1;i<=m;i++) f[i]=-inf;f[0]=0;
		c[n+1].t=0;
		double las=0,now,sii=0,si=0,res=0;
		for (i=1;i<=n;i++) {
			double k=c[i+1].t;
			if (c[i].dt!=0) {
				sii+=1.0*c[i].t*c[i].t/c[i].dt;
				si+=1.0*c[i].t/c[i].dt;
				res+=1.0/c[i].dt;
				now=si-k*res;
				now=min(now,(double)m);
				if (i==n) now=m;
				for (;j<=now;j++) {
					double k=1.0*(si-j)/res;
					f[j]=0.5*(sii-k*k*res);
				}
			}
			else {
				now=m;
				for (;j<=now;j++) {
					double k=c[i].t,l=1.0*si-k*res;
					f[j]=0.5*(sii-1.0*k*k*res)+(j-l)*c[i].t;
				}
			}//特判
			if (now>=m) break;
		}
	}
}
signed main(void){
	char ch;int i;
	read(n);read(m);
	for (i=1;i<=n;i++) {
		cin>>ch;
		if (ch=='D') ++cnt1,read(d[cnt1].w),read(d[cnt1].t),read(d[cnt1].dt);
		else ++cnt2,read(c[cnt2].t),read(c[cnt2].dt);
	}
	solve1::main();
	solve2::main();
	double ans=-inf;
	for (i=0;i<=m;i++) ans=max(solve1::f[i]+solve2::f[m-i],ans);
	if (ans<-1e14) puts("impossible");
	else printf("%.10lf\n",ans);
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 && ./$i