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;
}
05-08 15:19