sgu 104 Little Shop of Flowers

时间:2021-07-20 14:46:05

经典dp问题,花店橱窗布置,不再多说,上代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#define N 150
#define inf 0x7f7f7f7f
using namespace std; int n, m;
int val[N][N], f[N][N];
int fa[N][N]; void print(int now, int place)
{
if (now == ) printf("%d ", place);
else
{
print(now-, fa[now][place]);
if (now != n) printf("%d ", place);
else printf("%d\n", place);
}
} int main()
{
scanf("%d%d", &n, &m);
memset(val, , sizeof(val));
memset(f, -0x7f, sizeof(f));
for (int i = ; i <= m; ++i) f[][i] = ;
for (int i = ; i <= n; ++i)
for (int j = ; j <= m; ++j)
scanf("%d", &val[i][j]);
for (int i = ; i <= n; ++i)
for (int j = i; j <= m-n+i; ++j)
for (int k = i-; k < j; ++k)
if (f[i][j] < f[i-][k] + val[i][j])
{
f[i][j] = f[i-][k] + val[i][j];
fa[i][j] = k;
}
int ans, place;
ans = -inf;
for (int i = n; i <= m; ++i)
if (ans < f[n][i])
{
ans = f[n][i];
place = i;
}
printf("%d\n", ans);
print(n, place);
}