算法1
头一次写接近200行的dp,发篇题解纪念一下
C++ 代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 20;
int f[N][230][16][16][2][2];
int g[N][N];
int sum[N][N];
int n, m, k;
int main()
{
scanf("%d%d%d", &n, &m, &k);
if(k == 0){
printf("Oil : %d", 0);
return 0;
}
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j)
scanf("%d", &g[i][j]);
for(int i = 1; i <= n; ++ i)
for(int j = 1; j <= m; ++ j)
if(j == 1) sum[i][j] = g[i][j];
else sum[i][j] = sum[i][j - 1] + g[i][j];
for(int i = 1; i <= m; ++ i)
for(int j = i; j <= m; ++ j)
{
f[1][j - i + 1][i][j][0][0] = sum[1][j] - sum[1][i - 1];
f[1][j - i + 1][i][j][0][1] = sum[1][j] - sum[1][i - 1];
f[1][j - i + 1][i][j][1][0] = sum[1][j] - sum[1][i - 1];
f[1][j - i + 1][i][j][1][1] = sum[1][j] - sum[1][i - 1];
}
for(int i = 2; i <= n; ++ i)
for(int t = 1; t <= k; ++ t)
for(int l = 1; l <= m; ++ l)
for(int r = l; r <= m; ++ r)
{
if(r - l + 1 > t) continue;
int cnt = sum[i][r] - sum[i][l - 1];
if(r - l + 1 == t)
{
f[i][t][l][r][0][0] = cnt;
f[i][t][l][r][0][1] = cnt;
f[i][t][l][r][1][0] = cnt;
f[i][t][l][r][1][1] = cnt;
continue;
}
for(int u = 0; u < 4; ++ u)
{
if(u == 0)
{
for(int p = l; p <= r; ++ p)
for(int q = r; q <= m; ++ q)
f[i][t][l][r][0][0] = max(f[i][t][l][r][0][0],
max(f[i - 1][t - (r - l + 1)][p][q][0][0],
f[i - 1][t - (r - l + 1)][p][q][0][1]));
f[i][t][l][r][0][0] += cnt;
}
else if(u == 1)
{
for(int p = l; p <= r; ++ p)
for(int q = p; q <= r; ++ q)
f[i][t][l][r][0][1] = max(f[i][t][l][r][0][1],
f[i - 1][t - (r - l + 1)][p][q][0][1]);
f[i][t][l][r][0][1] += cnt;
}
else if(u == 2)
{
for(int p = 1; p <= l; ++ p)
for(int q = r; q <= m; ++ q)
f[i][t][l][r][1][0] = max(f[i][t][l][r][1][0],
max(
max(f[i - 1][t - (r - l + 1)][p][q][0][0],
f[i - 1][t - (r - l + 1)][p][q][0][1]),
max(f[i - 1][t - (r - l + 1)][p][q][1][0],
f[i - 1][t - (r - l + 1)][p][q][1][1])
)
);
f[i][t][l][r][1][0] += cnt;
}
else if(u == 3)
{
for(int p = 1; p <= l; ++ p)
for(int q = l; q <= r; ++ q)
f[i][t][l][r][1][1] = max(f[i][t][l][r][1][1],
max(f[i - 1][t - (r - l + 1)][p][q][0][1],
f[i - 1][t - (r - l + 1)][p][q][1][1]));
f[i][t][l][r][1][1] += cnt;
}
}
}
int ans = 0;
int x, cnt, yl, yr, p, q;
for(int i = 1; i <= n; ++ i)
for(int l = 0; l <= m; ++ l)
for(int r = l; r <= m; ++ r)
{
if(r - l + 1 > k) break;
ans = max(ans, max(max(f[i][k][l][r][0][0], f[i][k][l][r][0][1]),
max(f[i][k][l][r][1][0], f[i][k][l][r][1][1]) ) );
}
printf("Oil : %d\n", ans);
bool tag = false;
for(int i = 1; i <= n && tag == false; ++ i)
for(int l = 0; l <= m && tag == false; ++ l)
for(int r = l; r <= m && tag == false; ++ r)
{
if(r - l + 1 > k) break;
if(ans == f[i][k][l][r][0][0])
{
x = i, yl = l, yr = r, p = 0, q = 0, cnt = k;
tag = true;
break;
}
if(ans == f[i][k][l][r][0][1])
{
x = i, yl = l, yr = r, p = 0, q = 1, cnt = k;
tag = true;
break;
}
if(ans == f[i][k][l][r][1][0])
{
x = i, yl = l, yr = r, p = 1, q = 0, cnt = k;
tag = true;
break;
}
if(ans == f[i][k][l][r][1][1])
{
x = i, yl = l, yr = r, p = 1, q = 1, cnt = k;
tag = true;
break;
}
}
while(true)
{
for(int y = yl; y <= yr; ++ y) printf("%d %d\n", x, y);
cnt -= (yr - yl + 1);
ans -= sum[x][yr] - sum[x][yl - 1];
x --;
if(cnt == 0) break;
for(int l = 1; l <= m; ++ l)
for(int r = l; r <= m; ++ r)
{
if(((p == 1 && q == 0) || (p == 0 && q == 0)) && f[x][cnt][l][r][0][0] == ans)
{
yl = l, yr = r, p = 0, q = 0;
}
if(f[x][cnt][l][r][0][1] == ans)
{
yl = l, yr = r, p = 0, q = 1;
}
if((p == 1 && q == 0) && f[x][cnt][l][r][1][0] == ans)
{
yl = l, yr = r, p = 1, q = 0;
}
if(((p == 1 && q == 1) || (p == 1 && q == 0)) && f[x][cnt][l][r][1][1] == ans)
{
yl = l, yr = r, p = 1, q = 1;
}
}
}
return 0;
}
%%%