线性动态规划
#include <iostream>
#include <algorithm>
#include <cstring>
int main() {
int d, k;
std::cin >> d >> k;
int r[257], p[257];
for (int i = 1; i <= d; i++)
std::cin >> r[i] >> p[i];
static long long f[257][257];
memset(f, 0x7f, sizeof(f));
for (int v = 0; v < 256; v++)
for (int i = 1; i <= d; i++) {
long long sum_of_squared_errors = 0;
for (int j = i; j <= d; j++) {
sum_of_squared_errors += 1LL * (r[j] - v) * (r[j] - v) * p[j];
f[i][j] = std::min(f[i][j], sum_of_squared_errors);
}
}
static long long c[257][257];
memset(c, 0x7f, sizeof(c));
c[0][0] = 0;
for (int i = 1; i <= d; i++) {
for (int j = 1; j <= std::min(i, k); j++) {
for (int s = 0; s < i; s++)
c[i][j] = std::min(c[i][j], c[s][j - 1] + f[s + 1][i]);
}
}
std::cout << c[d][k] << std::endl;
return 0;
}