UVALive 6771 - Buffed Buffet （斜率优化）

题目链接： UVALIVE link2 有两种，一种离散的，一种连续的。离散的用斜率优化去DP，连续的暴力搞。题解参考： http://blog.brucemerry.org.za/2014/06/acm-icpc-2014.html

This one was deceptively sneaky, but the principles are reasonably simple. It’s not too hard to guess that one will solve the continuous and discrete problems separately, and then consider all partitions between the two.

Let’s start with the continuous problem, since it is a little easier. I don’t have a formal proof, but it shouldn’t be too hard to convince yourself that a greedy strategy works. We start by eating the tastiest food. Once it degrades to being as tasty as the second-tastiest food, we then each both, in the proportion that makes them decay at the same rate. In fact, at this point we can treat them as a combined food with a combined (slower) decay rate. We continue eating this mix until tastiness decays to match the third-tastiest, and so on. There are some corner cases that need to be handled if there are foods that don’t decay.

xiaodao的题解代码：

/* ***
Author :kuangbin
Created Time :2015/5/6 22:21:18
File Name :F:\ACM\2015ACM\比赛练习\2014final\B.cpp
************************************************ */

#include <stdio.h>

#include <string.h>

#include

#include <math.h>

#include <stdlib.h>

#include <time.h>
using namespace std;
const long long LINF = 1e18;
const double eps = 1e-8;
long long dp[2][10010];
int que[10010];
long long X[10010],Y[10010];
long long det(int k,int j,int i){
long long x1 = X[j] - X[k];
long long y1 = Y[j] - Y[k];
long long x2 = X[i] - X[k];
long long y2 = Y[i] - Y[k];
return x1*y2 - x2*y1;
}

int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int D,W;
while(scanf(“%d%d”,&D,&W) == 2){
int now = 0;
for(int i = 1;i <= W;i++){
dp[now][i] = -LINF;
}
dp[now][0] = 0;
vector<pair<int,int> >C;
while(D–){
char op[2];
scanf(“%s”,op);
if(op[0] == ‘D’){
int w,t,dt;
scanf(“%d%d%d”,&w,&t,&dt);
now ^= 1;
for(int i = 0;i <= W;i++)
dp[now][i] = -LINF;
int st,ed;
for(int c = 0;c < w;c++){
st = ed = 0;
for(int i = 0;iw+c <= W;i++){
if(dp[now^1][iw+c] > -LINF){
X[i] = i;
Y[i] = dp[now^1][i*w+c]-t*i-(long long)(i*i+i)/2*dt;
while(st+1 < ed && det(que[ed-2],que[ed-1],i) >= 0)ed–;
que[ed++] = i;
}
int k = -idt;
while(st+1 < ed && Y[que[st]]-k\X[que[st]] <= Y[que[st+1]]-k*X[que[st+1]])st++;
if(st < ed){
dp[now][i*w+c] = t*i - (long long)(i*i-i)/2*dt + Y[que[st]] - kX[que[st]];
}
}
}
}
else{
int t,dt;
scanf(“%d%d”,&t,&dt);
C.push_back(make_pair(t,dt));
}
}
if(C.size() == 0 && dp[now][W] == -LINF){
printf(“impossible\n”);
continue;
}
double ans = dp[now][W];
if(C.size() == 0){
printf(“%.10lf\n”,ans);
continue;
}
sort(C.begin(),C.end());
reverse(C.begin(),C.end());
int sz = C.size();
int i = 0;
int j = 0;
double cur = C[0].first;
double xx = 0;
double del = 0;
double ret = 0;
double px = 0.0;
while(i < W){
while(j < sz && C[j].first > cur-eps){
if(C[j].second == 0)del += 1e60;
else del += 1.0/C[j].second;
j++;
}
if(del > 1e30){
while(i < W){
ret += cur(i+1-max(1.0i,xx));
i++;
ans = max(ans,ret+dp[now][W-i]);
}
break;
}
if(j == sz){
while(i < W){
ret += (cur-1.0/del(max(1.0*i,xx)-xx)+cur-1.0/del*(i+1-xx))/2(i+1-max(1.0i,xx));
i++;
ans = max(ans,ret+dp[now][W-i]);
}
break;
}
double nv = C[j].first;
double nx = xx + (cur-nv)del;
while(i < W && i+1 < nx+eps){
ret += (cur-1.0/del(max(1.0*i,xx)-xx)+cur-1.0/del*(i+1-xx))/2(i+1-max(1.0i,xx));
i++;
px = i;
ans = max(ans,ret+dp[now][W-i]);
}
ret += (cur-1.0/del(px-xx)+nv)/2(nx-px);
px = nx;
xx = nx;
cur = nv;
}
printf(“%.10lf\n”,ans);
}
return 0;
}