WC2001 高性能计算机

cogs网址

这道题DP
设g[0/1][i][a][b]表示第i个机子做了a个A，b个B，0/1表示当前为A/B的最小代价 N^4转移
设f[i][a][b]表示前i个机子做了a个A，b个B的最小答案 N^5转移

# include <bits/stdc++.h>

# define RG register

# define IL inline

# define Fill(a, b) memset(a, b, sizeof(a))

# define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

using namespace std;

typedef long long ll;

const int _(70);

IL ll Read(){

    RG char c = getchar(); RG ll x = 0, z = 1;

    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

    return x * z;

}

int na, nb, p, ta[_], tb[_], ka[_], kb[_];

int g[2][_][_][_], f[_][_][_];

IL void Calc(RG int x){

    g[0][x][0][0] = g[1][x][0][0] = 0;

    for(RG int i = 0; i <= na; ++i)

        for(RG int j = 0; j <= nb; ++j){

            for(RG int k = 1; k <= i; ++k) g[0][x][i][j] = min(g[0][x][i][j], g[1][x][i - k][j] + ta[x] + ka[x] * k * k);

            for(RG int k = 1; k <= j; ++k) g[1][x][i][j] = min(g[1][x][i][j], g[0][x][i][j - k] + tb[x] + kb[x] * k * k);

        }

}

int main(RG int argc, RG char *argv[]){

    File("hpc");

    na = Read(); nb = Read(); p = Read();

    for(RG int i = 1; i <= p; ++i) ta[i] = Read(), tb[i] = Read(), ka[i] = Read(), kb[i] = Read();

    Fill(g, 127); Fill(f, 127); f[0][0][0] = 0;

    for(RG int i = 1; i <= p; ++i) Calc(i);

    for(RG int q = 1; q <= p; ++q)

        for(RG int i = 0; i <= na; ++i)

            for(RG int j = 0; j <= nb; ++j)

                for(RG int a = 0; a <= i; ++a)

                    for(RG int b = 0; b <= j; ++b)

                        f[q][i][j] = min(f[q][i][j], max(f[q - 1][i - a][j - b], min(g[0][q][a][b], g[1][q][a][b])));

    printf("%d\n", f[p][na][nb]);

    return 0;

}