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

#include

#include

#include

#include

#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;
int que;
long long X,Y;
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;
vector<pair<int,int> >C;
while(D–){
char op;
scanf(“%s”,op);
if(op == ‘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][i
w+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.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;
}

------ 本文结束------
• 本文作者： kuangbin
• 本文链接： 605.html
• 版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明出处！
0%