这道题的难点在于，前面分组的时间会影响到后面的结果
也就是有后效性，这样是不能用dp的 所以我们要想办法取消后效性 那么，我们就可以把影响加上去，也就是当前这一组加上了s 那么就把s对后面的影响全部加上 这个做法非常巧妙。#include#include #include #define REP(i, a, b) for(int i = (a); i < (b); i++)using namespace std;const int MAXN = 5123;int a[MAXN], t[MAXN], f[MAXN];int dp[MAXN], n, s;int main(){ scanf("%d%d", &n, &s); REP(i, 1, n + 1) { int x, y; scanf("%d%d", &x, &y); t[i] = t[i-1] + x; f[i] = f[i-1] + y; } memset(dp, 0x3f, sizeof(dp)); dp[0] = 0; REP(i, 1, n + 1) REP(j, 1, i + 1) //枚举最后一组的左端点 dp[i] = min(dp[i], dp[j-1] + (f[i] - f[j-1]) * t[i] + s * (f[n] - f[j-1])); printf("%d\n", dp[n]); return 0;}