🔍 解题思路

很明显的动态规划

我们假设dp[i][j]表示前i束花插入到前j个花瓶的最大美学价值，w[i][j]表示第i花插到第j号瓶子的美学价值

很容易推断出，dp[1][1] = w[1][1] ,dp[1][2] = max(dp[1][1],w[1][2]), dp[1][3] = max(dp[1][2],w[1][3]);

然后又2束花的时候：dp[2][1]这种情况是没有意义的，因为瓶子不够

dp[2][2] = dp[1][1]+w[2][2]，当dp[i][j]中i=j时，花刚好将瓶子插满

dp[2][3]，当dp[i][j]中i<j这种情况，我们可以这样认为，第i插入第j个瓶子中吗？

插入的话dp[2][3] = dp[1][2]+w[2][3]

不插入的话 dp[2][3] = dp[2][2]

两者比较一个最大值赋给dp[2][3]

所以由此我们能够推断出dp[i][j] = max(dp[i-1][j-1]+w[i][j]，dp[i][j-1])

当i==j时 dp[i][j] = dp[i-1][j-1]+w[i][j]；

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn =100+10;
int flo_vas[maxn][maxn];
int dp[maxn][maxn];
int f,v;
int main()
{
    scanf("%d%d",&f,&v);
    memset(flo_vas,0,sizeof(flo_vas));
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=f;++i)
        for(int j=1;j<=v;++j)
            scanf("%d",&flo_vas[i][j]);
    for(int i=1;i<=f;++i)
        for(int j=i;j<=v;++j)
        {
            if(i==j) dp[i][j]=dp[i-1][j-1]+flo_vas[i][j];
            else dp[i][j]=max(dp[i-1][j-1]+flo_vas[i][j],dp[i][j-1]);
        }
    printf("%d\n",dp[f][v]);
    return 0;
}