- #include#include#include using namespace std;
- const long long inf = 100000000000000000;
- const int maxn = 4200;
- int tt,
- n,
- now;
- long long t[maxn],
- p[maxn],
- sx[maxn],
- sy[maxn],
- s2x[maxn],
- s2y[maxn],
- s0x[maxn],
- s0y[maxn];
- long long dp[2][maxn][2];
- long long ans;
- int main() {
- //freopen("K.in","r",stdin);
- //freopen("K.out","w",stdout);
- scanf("%d", &tt);
- for (int q = 1; q <= tt; ++q) {
- scanf("%d", &n);
- sx[0] = 0;
- sy[0] = 0;
- s2x[0] = 0;
- s2y[0] = 0;
- s0x[0] = 0;
- s0y[0] = 0;
- for (int i = 1; i <= n; ++i) {
- scanf("%d%d", &t[i], &p[i]);
- sx[i] = sx[i - 1] + t[i];
- sy[i] = sy[i - 1] + p[i];
- s0x[i] = s0x[i - 1] + sx[i];
- s0y[i] = s0y[i - 1] + sy[i];
- }
- for (int i = 1; i <= n; ++i) {
- s2x[i] = s2x[i - 1] + t[i] * 2 * i;
- s2y[i] = s2y[i - 1] + p[i] * 2 * i;
- }
- memset(dp, 0, sizeof(dp));
- now = 1;
- for (int i = 2; i <= n; ++i) {
- for (int j = 1; j <= i - 2; ++j) dp[now][j][0] = dp[now ^ 1][j][0] + p[i] * (i - j);
- dp[now][i - 1][0] = s0x[i - 1] + p[i];
- for (int j = 1; j <= i - 2; ++j) dp[now][i - 1][0] = min(dp[now][i - 1][0], dp[now ^ 1][j][1] + p[i] - (s2x[i - 1] - s2x[(i - 1 + j) / 2] - (sx[i - 1] - sx[(i - 1 + j) / 2]) * (i + j)));
- for (int j = 0; j <= i - 2; ++j) dp[now][j][1] = dp[now ^ 1][j][1] + t[i] * (i - j);
- dp[now][i - 1][1] = s0y[i - 1] + t[i];
- for (int j = 1; j <= i - 2; ++j) dp[now][i - 1][1] = min(dp[now][i - 1][1], dp[now ^ 1][j][0] + t[i] - (s2y[i - 1] - s2y[(i - 1 + j) / 2] - (sy[i - 1] - sy[(i - 1 + j) / 2]) * (i + j)));
- now = now ^ 1;
- }
- now = now ^ 1;
- ans = inf;
- for (int i = 1; i <= n - 1; ++i) {
- ans = min(ans, dp[now][i][1]),
- ans = min(ans, dp[now][i][0]);
- }
- cout << "Case #" < ": " < endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2118488.html