首页 > 学院 > 开发设计 > 正文

POJ - 1157 LITTLE SHOP OF FLOWERS解题报告

2019-11-10 17:24:02
字体:
来源:转载
供稿:网友
题目大意:给你f(1-100)个花和v(1-100)个花瓶,然后给你一个表,给出了每朵花放到每个花瓶中的可以获得的好感度(可能是负的),问你怎么放可以获得最大的好感度。要求:编号小的花放的花瓶的编号一定要比编号大的花放进的花瓶的编号小。注意:花瓶好像是要比花多的(至少一样多)思路:设a[i][j]表示前i个花全都放到前j个花瓶中最多可得到的好感度。递推关系:a[i][j]=max{a[i-1][j],a[i-1][j-1]+v[i][j]}

边界条件:a[1][i]=max{v[1][j](1<=j<=i)};a[i][j]=-inf(i>j);

注:因为边界没有好好想,wa了两次才ac,罪过啊。


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表