题目链接

一开始我的\(dp\)方程列错了，其实也不能说列错了，毕竟我交上去还是把暴力的分都拿到了，只是和题解的不一样，然后搞半天没搞出来去看题解，又看不懂，对不上，原来状态设置不一样自闭了。

\(f[i]=all-sum[j]*dis[j]-(sum[i]-sum[j])*dis[i]\)

\(f[i]=all-sum[j]*dis[j]-sum[i]*dis[i]+sum[j]*dis[i]\)

\(sum[j]*dis[j]=dis[i]*sum[j]-sum[i]*dis[i]+all-f[i]\)

#include <cstdio>

const int MAXN = 20010;

#define ll long long

inline ll min(const ll a, const ll b){

	return a < b ? a : b;

}

int n;

ll all, ans = 1e17, sum[MAXN], dis[MAXN];

int w[MAXN], d[MAXN];

int q[MAXN], head, tail;

inline double k(int i, int j){

	return ((double)sum[i] * dis[i] - sum[j] * dis[j]) / (sum[i] - sum[j]);

}

int main(){

	scanf("%d", &n);

	for(int i = 1; i <= n; ++i)

	   scanf("%d%d", &w[i], &d[i]);

	for(int i = n; i; --i)

	   all += w[i] * (dis[i] = dis[i + 1] + d[i]);

	for(int i = 1; i <= n; ++i)

	   sum[i] = sum[i - 1] + w[i];

	for(int i = 1; i <= n; ++i){

	   while(head < tail && k(q[head], q[head + 1]) > dis[i]) ++head;

	   int j = q[head];

	   ans = min(ans, all - sum[j] * dis[j] - (sum[i] - sum[j]) * dis[i]);

	   while(head < tail && k(q[tail - 1], q[tail]) <= k(q[tail], i)) --tail;

	   q[++tail] = i;

    }

    printf("%lld\n", ans);

    return 0;

}