作者:Yvette-XY | 来源:互联网 | 2023-07-06 10:17
找到原题。游戏(game.cppcpas)【题目描述】有n个数,编号从1到n。现在把n个数分成k组编号为1到k,使得每组内的数必须连续,组与组之间不能相交并且每个数必须属于一个组。
找到原题。
游戏 (game.cpp/c/pas)
【题目描述】
有n个数,编号从1到n。现在把n个数分成k组编号为1到k,使得每组内的数必须连续,组与组之间不能相交并且每个数必须属于一个组。
游戏进行的过程如下:
1. 如果n个数都已经获得了,游戏结束。否则,找到编号最小没有全部获得的组X。
2. 游戏系统会给一个空的盒子,对于组X中已经获得的数i,将ti张写着数i的卡片放入盒子中,对于组X中最小的没有获得的数j,将tj张写着数j的卡片放入盒子中。
3. 随机从盒子中抽取一张卡片,表示当前获得的数字,然后等待1小时的冷却时间后跳转到过程1。
现在需要确定一个最好的分组,使得这个游戏期望结束的时间最小。
【输入格式】
第一行两个整数n,k。
第二行n个整数,第i个整数为ti。
【输出格式】
一行,游戏结束的最小期望时间,保留小数点后两位。
【样例输入】
4 2
100 3 5 7
【样例输出】
5.74
【数据范围】
对于30%的数据, 1 <= n <= 20。
对于100%的数据,1 <= n <= 200000, 1 <= k <= min(50, n),1 <= ti <= 100000。 【样例解释】
分组方式为{100},{3,5,7}。
思考
抄一份抄别人题解的题解。。。。
其实解释得很清楚,gyk(doggu)问我为什么不能直接上单调队列优化(不用斜率),其实很多时候分不清的情况就是在比较i与j时我们很容易比较出哪个优秀,但是如果存在k使得与i比较时
valik!=valij
,那么证明比较的双方互成对方的某一系数,那么比较就不能一概而论,需要用单调队列优化了。
#include
using namespace std;
const int N = 2e5+5;
double exc[N] = {0}, sum[N] = {0}, rev[N] = {0};
double t[N];
double dp[N][55];
inline double y(int x, int p){
return dp[x][p] - exc[x] + sum[x]*rev[x];
}
inline double g(int j, int k, int p){
return (y(j, p)-y(k, p))/(sum[j]-sum[k]);
}
inline double cal(int l, int i){
return exc[i]-exc[l]-(rev[i]-rev[l])*sum[l];
}
int q[N], top, tail;
inline void add(int i, int k){
while(top 1 && g(i, q[tail-1], k) 1], q[tail-2], k)) tail--;
q[tail++] = i;
}
inline int getmax(int i, int k){
while(top 1 && g(q[top+1], q[top], k) return q[top];
}
int main(){
int n, K;
scanf("%d%d", &n, &K);
for(int i = 1; i <= n; ++i) scanf("%lf", t+i);
for(int i = 1; i <= n; ++i){
sum[i] = sum[i-1] + t[i];
rev[i] = rev[i-1] + 1.0/t[i];
exc[i] = exc[i-1] + sum[i]/t[i];
}
for(int i = 1; i <= n; ++i) dp[i][1] = exc[i];
for(int k = 2; k <= K; ++k){
top = tail = 0;
q[tail++] = 0;
for(int i = 1; i <= n; ++i) add(i, k-1);
for(int i = 1; i <= n; ++i){
if(i >= k){
int l = getmax(i, k-1);
dp[i][k] = dp[l][k-1] + cal(l, i);
}
else dp[i][k] = 1e50;
}
}
printf("%.2f\n", dp[n][K]);
}