首页 > 其他 > 详细

tyvj1124花店橱窗——有限制的DP

时间:2018-02-21 22:43:41      阅读:250      评论:0      收藏:0      [点我收藏+]

题目:http://www.joyoi.cn/problem/tyvj-1124

此题首先注意一束花能往哪些花瓶中放置:原本应放在本位置,但因为有多余花瓶,故可以有些变动,范围在i~i+v-f间;

假设选择此花瓶,则对其上一束花的摆放位置有要求:放在此花瓶之前;故再用k循环一遍;

输出路径在上一步中记录,只需以角标记录此花这种摆放方式对应的上一束花的摆放位置,递归输出即可。

代码如下:

#include<iostream>
#include<cstdio>
using namespace std;
int f,v,w[105][105],path[105][105],dp[105][105],ans,p;
void print(int i,int j)
{
	if(!i)return;
	print(i-1,path[i][j]);
	printf("%d ",j);
}
int main()
{
	scanf("%d%d",&f,&v);
	for(int i=1;i<=f;i++)
		for(int j=1;j<=v;j++)
			scanf("%d",&w[i][j]);
	for(int i=1;i<=f;i++)
	{
		int up=i+v-f;
		for(int j=i;j<=up;j++)
		{
			dp[i][j]=dp[i-1][i-1]+w[i][j];//!
			path[i][j]=i-1;//!
			for(int k=i;k<j;k++)//不能k=i-1! 
			{
				if(dp[i][j]<dp[i-1][k]+w[i][j])
				{
					dp[i][j]=dp[i-1][k]+w[i][j];
					path[i][j]=k;
				}
			}
		}
	}
	for(int i=f;i<=v;i++)
	{
		if(dp[f][i]>ans)
		{
			ans=dp[f][i];
//			p=path[f][i];
			p=i;
		}
	}
	printf("%d\n",ans);
	print(f,p);
	return 0;
}

  

tyvj1124花店橱窗——有限制的DP

原文:https://www.cnblogs.com/Zinn/p/8457552.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!