t[i]表示第i只小猫玩耍的时间,d[i]表示第i只小猫到起点的路程
设a[i] = t[i] - d[i]
按a[i]排序
f[i][j] 表示前i个饲养员,最后接的小猫是j
s表示a的前缀和
f[i][j] = f[i - 1][k] + aj - (s[j] - s[k]);
移项
f[i - 1][k] + s[k] = a[j]k + f[i][j] - a[j]*j + s[j]
因为斜率单增,k单增,所以应用单调队列维护凸包,并找出第一个斜率大于当斜率的点,转移即可
还是要搞清更变量是什么含义,LL开全
开始一步转化还是比较神奇的,给你一大堆东西找出来真正有用的是啥
这题每个猫有用的其实就是可以开始接的时间,路程和时间直接转化到一起即可
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5,M = N,P = 110;
int d[N],n,m,p,q[N];
LL a[N],s[N],f[P][N];
LL get_y(int i,int j)
{
return f[i - 1][j] + s[j];
}
int main()
{
cin >> n >> m >> p;
for(int i = 2;i <= n;i ++)
scanf("%d",&d[i]),d[i] += d[i - 1];
for(int i = 1;i <= m;i ++)
{
int hi,ti;
scanf("%d%d",&hi,&ti);
a[i] = ti - d[hi];
}
sort(a + 1,a + 1 + m);
for(int i = 1;i <= m;i ++)
s[i] = s[i - 1] + a[i];
memset(f,0x3f,sizeof f);
for(int i = 0;i <= p;i ++)
f[i][0] = 0;
for(int i = 1;i <= p;i ++)
{
int tt = 0,hh = 0;
for(int j = 1;j <= m;j ++)
{
while(tt > hh && get_y(i,q[hh + 1]) - get_y(i,q[hh]) <= a[j] * (q[hh + 1] - q[hh]))hh ++;
int k = q[hh];
f[i][j] = f[i - 1][k] + (j - k) * a[j] - (s[j] - s[k]);
while(tt > hh && (get_y(i,q[tt]) - get_y(i,q[tt - 1])) * (j - q[tt])>= (get_y(i,j) - get_y(i,q[tt])) * (q[tt] - q[tt - 1]))tt --;
q[++ tt] = j;
}
}
cout << f[p][m];
}
请问为什么a要开long long呀
实测,a不开long long会溢出
666