这道题没有打卡,所以自己写一下方便以后回来看
$m$ 个花瓶, $n$ 朵花。给出每朵花插入花瓶的价值,且 插花的顺序和花的编号一致。
解法: 01
背包
$f(i,j)$ :如果理解清楚题意的话就很好做了,我们前 $i$ 个物品,且在 前 $j$ 个花瓶中插,
状态划分: 根据倒数第二个花插入的位置来划分
当$i==j$时我们必须插入这个花瓶,
$j >i$我们中间可以有空隙,f[i][j]=f[i-1][j-1] +g[i][j]
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n,m;
int g[N][N],f[N][N];
void dfs(int i,int j)
{
if(!i) return;
while(j && f[i][j] == f[i][j - 1]) j --;
dfs(i - 1,j - 1);
cout << j <<' ';
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
cin >> g[i][j];
for(int i = 1;i <= n;i ++)
for(int j = i;j <= m;j ++)
if(i == j) f[i][j] = f[i - 1][j - 1] + g[i][j];
else f[i][j] = max(f[i - 1][j - 1] + g[i][j], f[i][j - 1]);
cout << f[n][m] << endl;
dfs(n,m);
return 0;
}
解法: 01
背包
状态表示$f(i,j)$:前$i$ 个花瓶,且$j$ 个花瓶必须插入花
状态划分:$f(i,j)$根据i-1
插入的位置来划分。当然我们必须从i
位置开始插
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n,m;
int g[N][N],f[N][N];
int ans[N][N];
void dfs(int i,int j)
{
if(!i) return;
dfs(i - 1, ans[i][j]);
cout << j << ' ';
}
int main()
{
cin >> n >> m;
for(int i = 1;i <= n;i ++)
for(int j = 1;j <= m;j ++)
cin >> g[i][j];
memset(f, -0x3f, sizeof f);
for(int i = 0;i <= m;i ++ ) f[0][i] = 0;
for(int i = 1;i <= n;i ++)
{
int maxv = i - 1;
for(int j = i;j <= m;j ++)
{
if(f[i - 1][maxv] < f[i - 1][j - 1]) maxv = j - 1;
f[i][j] = f[i - 1][maxv] + g[i][j];
ans[i][j] = maxv;
}
}
int res = n;
for(int i = n;i <= m;i ++ ) if(f[n][res] < f[n][i]) res = i;
cout << f[n][res] << endl;
dfs(n,res);
return 0;
}