网站开发研究背景,北京建展科技发展有限公司,哪个平台购物质量好又便宜,wordpress和织梦百度收录Description 假设你想以最美观的方式布置花店的橱窗。你有F束花#xff0c;每束花的品种都不一样#xff0c;同时#xff0c;你至少有同样数量的花瓶#xff0c;被按顺序摆成一行。花瓶的位置是固定的#xff0c;并从左至右#xff0c;从1至V顺序编号#xff0c;V是花瓶…Description 假设你想以最美观的方式布置花店的橱窗。你有F束花每束花的品种都不一样同时你至少有同样数量的花瓶被按顺序摆成一行。花瓶的位置是固定的并从左至右从1至V顺序编号V是花瓶的数目编号为1的花瓶在最左边编号为V的花瓶在最右边。花束则可以移动并且每束花用1至F的整数唯一标识。标识花束的整数决定了花束在花瓶中排列的顺序即如果Ij则花束I必须放在花束j左边的花瓶中。 例如假设杜鹃花的标识数为1秋海棠的标识数为2康乃馨的标识数为3所有的花束在放入花瓶时必须保持其标识数的顺序即杜鹃花必须放在秋海棠左边的花瓶中秋海棠必须入在康乃馨左边的花瓶中如果花瓶的数目大于花束的数目则多余的花瓶必须空置每个花瓶中只能放一束花。 每一个花瓶的形状和颜色也不相同。因此当各个花瓶中放入不同的花束时会产生不同的美学效果并以美学值一个整数来表示空置花瓶的美学值为零。在上述例子中花瓶与花束的不同搭配所具有的美学值可以用下面式样的表格来表示。 花瓶1 花瓶2 花瓶3 花瓶4 花瓶5 杜鹃花 7 23 -5 -24 16 秋海棠 5 21 -4 10 23 康乃馨 -21 5 -4 -20 20 例如根据上表杜鹃花放在花瓶2中会显得非常好看但若放在花瓶4中则显得很难看。 为取得最佳美学效果你必须在保持花束顺序的前提下使花束的摆放取得最大的美学值。如果具有最大美学值的摆放方式不止一种则其中任何一种摆放方式都可以接受但你只右输出其中一种摆放方式。 假设条件Asumption 1≤F≤100其中F为花束的数量花束编号从1至F。 F≤V≤100其中V是花瓶的数量。 -50≤Aij≤50其中Aij 是花束i在花瓶j中时的美学值。 Input
第一行包含两个数F、V。 随后的F行中每行包含V个整数Aij即为输入文件中第i1行中的第j个数。
Output
文件应包含两行 第一行是程序所产生摆放方式的美学值。 第二行必须用F个数表示摆放方式即该行的第K个数表示花束K所在的花瓶的编号。 Sample Input
3 5 7 23 -5 -24 16 5 21 -4 10 23 -21 5 -4 -20 20
Sample Output
53 2 4 5 解题思路
我们用f[i][j]表示前i朵花插在第j个花盆里的最优解然后用数字金字塔的方法不过这里枚举一个k因为可以从多个方向来方案数可以用我之前黑暗破坏神的方法用b[i][j]来表示上一层选的之后回退就ok了。动态转移方程f[i][j]f[i-1][k]a[i][j] 代码
#includecstdio
#includeiostream
using namespace std;
int n,m,a[102][102],f[102][102],maxs,b[102][102],sz,k[102];
void print(int x,int y)//附递归回退法
{if (y1) return;print(b[y][x],y-1);printf(%d ,b[y][x]);
}
int main()
{scanf(%d%d,n,m);for (int i1;in;i)for (int j1;jm;j){scanf(%d,a[i][j]);//输入}for (int i1;im-n1;i) f[1][i]a[1][i];//第一朵花插在第i个花盆的最优值就是它本身的价值for (int i2;in;i){//插入第i朵花for (int ji;jm-ni;j){//枚举插在第几个花盆for (int ki-1;kj;k){//枚举上一层插在第几个if (f[i-1][k]a[i][j]f[i][j]){//如果发现更优的解f[i][j]f[i-1][k]a[i][j];//加上当前价值b[i][j]k;//记录选择}}}}maxs-2100000000;for (int in;im;i) {if (f[n][i]maxs)//找最后一行的最优解{maxsf[n][i];szi;}}printf(%d\n,maxs);//输出最优解for (int i1;in;i) {k[i]sz;//记录这个选的花瓶szb[n-i1][sz];//退回上一朵花}for (int in;i1;i--) printf(%d ,k[i]);//输出方案
}
