首页 > 代码库 > poj 1157 LITTLE SHOP OF FLOWERS

poj 1157 LITTLE SHOP OF FLOWERS

2024-07-11 19:40:20   217人阅读

题意为F束花插入V个瓶子里面，花要按编号递增顺序插，不同花插入不同的花瓶有不同的美观程度，要求最大的美观程度。

一种f[i][j]表示第i束花插入第[j]个瓶子里面所获得的最大的美观程度。则状态转移函数可以表示为f[i][j]=max(f[i-1][k]+a[i][j])其中i-1<=k<j;

则输出为f[F][F]-f[F][V]之间的最大值。

第二种解法的状态函数为f[i][j]表示第i束花插入前j个瓶子里面。则状态转移函数为f[i][j]=max(f[i-1][j-1]+a[i][j],f[i][j-1])

因为有两种插法，一：第i束花插入第j个瓶子里面，则为f[i][j]=f[i-1][j-1]+a[i][j].二：第i束花不插入第j个瓶子里面，则f[i][j]=f[i][j-1]。两者当中取极大者

#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define maxn 120#define inf 10000000int mk[maxn][maxn];int dp[maxn][maxn];int f,v;int main(){    while(scanf("%d%d",&f,&v)!=EOF)    {        int i,j;        for(i=1;i<=f;i++)        {            for(j=1;j<=v;j++)                scanf("%d",&mk[i][j]);            dp[i][i]=dp[i-1][i-1]+mk[i][i];        }        for(i=1;i<=f;i++)            for(j=i+1;j<=v;j++)                dp[i][j]=max(dp[i][j-1],dp[i-1][j-1]+mk[i][j]);        printf("%d\n",dp[f][v]);    }    return 0;}
View Code

 

 


联系
我们