不知道为啥,这道题好像不用理解斜率优化也可以通过滴~
#include<cstring>
#include<iostream>
using namespace std;
int n,m,a[5005],b[5005],f[5005];
int main()
{
int i,j;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d%d",&b[i],&a[i]);
b[i]+=b[i-1],a[i]+=a[i-1];
}
memset(f,0x3f,sizeof f);
f[0]=0;
for(i=1;i<=n;i++)for(j=0;j<i;j++)f[i]=min(f[i],f[j]+(a[i]-a[j])*b[i]+m*(a[n]- a[j]));
printf("%d\n",f[n]);
return 0;
}