长乐 Day 9

今天上区间DP和背包
果然如某谷所说，今日适合好好打题，不适合骗分
区间DP直接每题都打满了
太简单了

wbz都会写

#include <bits/stdc++.h>
using namespace std;
const int L = 20;
const double INF = INT_MAX;
double n;
double s[L][L];
double dp[L][L][L][L][L];
double K;
double do_ans(int x, int y, int a, int b) {
    double sum = s[a][b] - s[a][y - 1] - s[x - 1][b] + s[x - 1][y - 1] - K;
    return sum * sum / n;
}
double f(int x, int y, int a, int b, int k) {
    double &Q = dp[x][y][a][b][k];
    if (Q >= 0)
        return Q;
    if (k == 1)
        return Q = do_ans(x, y, a, b);
    Q = INF;
    for (int i = x; i < a; i++)
        Q = min(Q, f(x, y, i, b, k - 1) + do_ans(i + 1, y, a, b)),
        Q = min(Q, f(i + 1, y, a, b, k - 1) + do_ans(x, y, i, b));
    for (int i = y; i < b; i++)
        Q = min(Q, f(x, y, a, i, k - 1) + do_ans(x, i + 1, a, b)),
        Q = min(Q, f(x, i + 1, a, b, k - 1) + do_ans(x, y, a, i));
    return Q;
}
void init() { memset(dp, -1, sizeof dp); }
int main(void) {
    cin >> n;
    for (int i = 1; i <= 8; i++) {
        for (int j = 1; j <= 8; j++) {
            cin >> s[i][j];
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    init();
    K = (double)s[8][8] / n;
    printf("%.3f", sqrt(f(1, 1, 8, 8, n)));
    return 0;
}

虽然一开始我TLE了

#include <bits/stdc++.h>
using namespace std;
const int L = 20;
const double INF = INT_MAX;
double n;
double s[L][L];
double dp[L][L][L][L][L];
double K;
double do_ans(int x, int y, int a, int b) {
    double sum = s[a][b] - s[a][y - 1] - s[x - 1][b] + s[x - 1][y - 1] - K;
    return sum * sum / n;
}
double f(int x, int y, int a, int b, int k) {
    double Q = dp[x][y][a][b][k];
    if (Q >= 0)
        return Q;
    if (k == 1)
        return Q = do_ans(x, y, a, b);
    Q = INF;
    for (int i = x; i < a; i++)
        Q = min(Q, f(x, y, i, b, k - 1) + do_ans(i + 1, y, a, b)),
        Q = min(Q, f(i + 1, y, a, b, k - 1) + do_ans(x, y, i, b));
    for (int i = y; i < b; i++)
        Q = min(Q, f(x, y, a, i, k - 1) + do_ans(x, i + 1, a, b)),
        Q = min(Q, f(x, i + 1, a, b, k - 1) + do_ans(x, y, a, i));
    return Q;
}
void init() { memset(dp, -1, sizeof dp); }
int main(void) {
    cin >> n;
    for (int i = 1; i <= 8; i++) {
        for (int j = 1; j <= 8; j++) {
            cin >> s[i][j];
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
        }
    }
    init();
    K = (double)s[8][8] / n;
    printf("%.3f", sqrt(f(1, 1, 8, 8, n)));
    return 0;
}

总之，“长了”的空气甚是香甜