勘误:
* 最初状态转移方程后面少了一个 $cost$,应该为 $cost\cdot sumf(n)-sumf(j-1)$
* 化简后的状态转移方程少加了一个 $dp(j)$。
另附 $O(n^2)$ 代码,可过:
```cpp
#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
inline int read()
{
int x = 0; bool op = 0;
char c = getchar();
while(!isdigit(c))op |= (c == '-'), c = getchar() ;
while(isdigit(c))x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return op ? -x : x;
}
const int N = 5010;
int n, s;
int sumt[N], sumf[N], dp[N];
int main()
{
n = read(); s = read();
for(int i = 1; i <= n; i++)
{
sumt[i] = read(); sumf[i] = read();
sumt[i] += sumt[i - 1]; sumf[i] += sumf[i - 1];
}
memset(dp, 0x3f, sizeof(dp));
dp[n + 1] = 0;
for(int i = n; i >= 1; i--)
{
for(int j = n + 1; j > i; j--)
{
int cost = sumt[j - 1] - sumt[i - 1] + s;
dp[i] = min(dp[i], dp[j] + cost * (sumf[n] - sumf[i - 1]));
}
}
printf("%d", dp[1]);
return 0;
}
```
by __gcd @ 2020-08-30 15:28:10
继续勘误:
* 状态的定义出现歧义,应该为`完成i后面(包括i)的所有任务的最小花费`
by __gcd @ 2020-08-30 15:29:21