Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

我也觉得是dfs暴力搜索，然后加上一些剪枝优化即可，0MS

Posted by hujk2008 at 2012-09-15 01:00:36 on Problem 1062
In Reply To:最关键的是图的表示+图的遍历，没用最短路径，直接遍历0MS Posted by:zjwzh at 2011-07-24 14:20:39

#include <stdio.h>
#include <string.h>

#define MAXLEN 102
#define _abs_(a) ((a)>=0?(a):-(a))

typedef struct st_goods
{
	int nPrice ;
	int nLevel ;
	int nAlterCount ;
	int nGoodsID[MAXLEN] ;
	int nGoodsOffPrice[MAXLEN] ;
}goods;

class CCaculateGoods
{
public:
	void    Input() ;
	int		Solve() ;
	int     dfs(int nMinlevel, int nMaxLevel,int nCosts, int nNeedGoodsID) ;
public:
	int		m_nGoodsCount ;
	goods   m_GoodsInfo[MAXLEN] ;
	int		m_nMaxLevelGap ;
	// 当前最优解
	int		m_nCurOptPrice ;
	int		m_nGoodsVisit[MAXLEN];
};


void CCaculateGoods::Input() 
{
	int i ,j ;
	scanf("%d%d",&m_nMaxLevelGap,&m_nGoodsCount) ;
	for ( i = 0 ; i < m_nGoodsCount ;i ++)
	{
		scanf("%d%d%d",&m_GoodsInfo[i].nPrice,&m_GoodsInfo[i].nLevel,&m_GoodsInfo[i].nAlterCount) ;
		for( j = 0 ;j < m_GoodsInfo[i].nAlterCount; j ++ )
		{
			scanf("%d%d",&m_GoodsInfo[i].nGoodsID[j],&m_GoodsInfo[i].nGoodsOffPrice[j]) ;
			m_GoodsInfo[i].nGoodsID[j] -- ;
		}
	}
}

int	CCaculateGoods::Solve() 
{
	m_nCurOptPrice = m_GoodsInfo[0].nPrice ;
	memset(m_nGoodsVisit,0,sizeof(m_nGoodsVisit)) ;
	return dfs(m_GoodsInfo[0].nLevel,m_GoodsInfo[0].nLevel,0,0) ;
}

int CCaculateGoods::dfs(int nMinlevel, int nMaxLevel,int nCosts, int nNeedGoodsID) 
{
	int nLevel , nNewCosts, i ;

	// 优化
	if( nCosts >= m_nCurOptPrice)
		return m_nCurOptPrice ;
	// 判断是否可以交易
	nLevel = m_GoodsInfo[nNeedGoodsID].nLevel ;
#if 0
	if( _abs_(nLevel-nMinlevel) > m_nMaxLevelGap )
		return m_nCurOptPrice ;
	if( _abs_(nLevel-nMaxLevel) > m_nMaxLevelGap )
		return m_nCurOptPrice ;

	// 是否有环路
	if( m_nGoodsVisit[nNeedGoodsID] == 1)
		return m_nCurOptPrice ;
#endif
	// 直接买这个物品的话
	nNewCosts = nCosts + m_GoodsInfo[nNeedGoodsID].nPrice ;
	if( nNewCosts < m_nCurOptPrice)
		m_nCurOptPrice = nNewCosts ;
	nMinlevel = nMinlevel <= nLevel ? nMinlevel:nLevel ;
	nMaxLevel = nMaxLevel >= nLevel ? nMaxLevel:nLevel ;
	m_nGoodsVisit[nNeedGoodsID] = 1 ;
	// 假如使用优惠
	for( i = 0 ;i < m_GoodsInfo[nNeedGoodsID].nAlterCount; i ++)
	{
		// 
		nNewCosts = nCosts+m_GoodsInfo[nNeedGoodsID].nGoodsOffPrice[i];
		if( nNewCosts >= m_nCurOptPrice)
			continue ;
		nLevel = m_GoodsInfo[m_GoodsInfo[nNeedGoodsID].nGoodsID[i]].nLevel ;
		if( _abs_(nLevel-nMinlevel) > m_nMaxLevelGap )
			continue ;
		if( _abs_(nLevel-nMaxLevel) > m_nMaxLevelGap )
			continue ;
		if( m_nGoodsVisit[m_GoodsInfo[nNeedGoodsID].nGoodsID[i]] == 1)
			continue ;
		dfs(nMinlevel,nMaxLevel,nCosts+m_GoodsInfo[nNeedGoodsID].nGoodsOffPrice[i],
			m_GoodsInfo[nNeedGoodsID].nGoodsID[i]) ;
	}
	// 恢复
	m_nGoodsVisit[nNeedGoodsID] = 0 ;
	return m_nCurOptPrice ;
}

int main()
{
	CCaculateGoods s ;
	s.Input() ;
	printf("%d\n",s.Solve()) ;
	return 0 ;
}

Followed by:

Post your reply here:

User ID:
Password:
Title:

Content:

> 
> #include <stdio.h>
> #include <string.h>
> 
> #define MAXLEN 102
> #define _abs_(a) ((a)>=0?(a):-(a))
> 
> typedef struct st_goods
> {
> 	int nPrice ;
> 	int nLevel ;
> 	int nAlterCount ;
> 	int nGoodsID[MAXLEN] ;
> 	int nGoodsOffPrice[MAXLEN] ;
> }goods;
> 
> class CCaculateGoods
> {
> public:
> 	void    Input() ;
> 	int		Solve() ;
> 	int     dfs(int nMinlevel, int nMaxLevel,int nCosts, int nNeedGoodsID) ;
> public:
> 	int		m_nGoodsCount ;
> 	goods   m_GoodsInfo[MAXLEN] ;
> 	int		m_nMaxLevelGap ;
> 	// 当前最优解
> 	int		m_nCurOptPrice ;
> 	int		m_nGoodsVisit[MAXLEN];
> };
> 
> 
> void CCaculateGoods::Input() 
> {
> 	int i ,j ;
> 	scanf("%d%d",&m_nMaxLevelGap,&m_nGoodsCount) ;
> 	for ( i = 0 ; i < m_nGoodsCount ;i ++)
> 	{
> 		scanf("%d%d%d",&m_GoodsInfo[i].nPrice,&m_GoodsInfo[i].nLevel,&m_GoodsInfo[i].nAlterCount) ;
> 		for( j = 0 ;j < m_GoodsInfo[i].nAlterCount; j ++ )
> 		{
> 			scanf("%d%d",&m_GoodsInfo[i].nGoodsID[j],&m_GoodsInfo[i].nGoodsOffPrice[j]) ;
> 			m_GoodsInfo[i].nGoodsID[j] -- ;
> 		}
> 	}
> }
> 
> int	CCaculateGoods::Solve() 
> {
> 	m_nCurOptPrice = m_GoodsInfo[0].nPrice ;
> 	memset(m_nGoodsVisit,0,sizeof(m_nGoodsVisit)) ;
> 	return dfs(m_GoodsInfo[0].nLevel,m_GoodsInfo[0].nLevel,0,0) ;
> }
> 
> int CCaculateGoods::dfs(int nMinlevel, int nMaxLevel,int nCosts, int nNeedGoodsID) 
> {
> 	int nLevel , nNewCosts, i ;
> 
> 	// 优化
> 	if( nCosts >= m_nCurOptPrice)
> 		return m_nCurOptPrice ;
> 	// 判断是否可以交易
> 	nLevel = m_GoodsInfo[nNeedGoodsID].nLevel ;
> #if 0
> 	if( _abs_(nLevel-nMinlevel) > m_nMaxLevelGap )
> 		return m_nCurOptPrice ;
> 	if( _abs_(nLevel-nMaxLevel) > m_nMaxLevelGap )
> 		return m_nCurOptPrice ;
> 
> 	// 是否有环路
> 	if( m_nGoodsVisit[nNeedGoodsID] == 1)
> 		return m_nCurOptPrice ;
> #endif
> 	// 直接买这个物品的话
> 	nNewCosts = nCosts + m_GoodsInfo[nNeedGoodsID].nPrice ;
> 	if( nNewCosts < m_nCurOptPrice)
> 		m_nCurOptPrice = nNewCosts ;
> 	nMinlevel = nMinlevel <= nLevel ? nMinlevel:nLevel ;
> 	nMaxLevel = nMaxLevel >= nLevel ? nMaxLevel:nLevel ;
> 	m_nGoodsVisit[nNeedGoodsID] = 1 ;
> 	// 假如使用优惠
> 	for( i = 0 ;i < m_GoodsInfo[nNeedGoodsID].nAlterCount; i ++)
> 	{
> 		// 
> 		nNewCosts = nCosts+m_GoodsInfo[nNeedGoodsID].nGoodsOffPrice[i];
> 		if( nNewCosts >= m_nCurOptPrice)
> 			continue ;
> 		nLevel = m_GoodsInfo[m_GoodsInfo[nNeedGoodsID].nGoodsID[i]].nLevel ;
> 		if( _abs_(nLevel-nMinlevel) > m_nMaxLevelGap )
> 			continue ;
> 		if( _abs_(nLevel-nMaxLevel) > m_nMaxLevelGap )
> 			continue ;
> 		if( m_nGoodsVisit[m_GoodsInfo[nNeedGoodsID].nGoodsID[i]] == 1)
> 			continue ;
> 		dfs(nMinlevel,nMaxLevel,nCosts+m_GoodsInfo[nNeedGoodsID].nGoodsOffPrice[i],
> 			m_GoodsInfo[nNeedGoodsID].nGoodsID[i]) ;
> 	}
> 	// 恢复
> 	m_nGoodsVisit[nNeedGoodsID] = 0 ;
> 	return m_nCurOptPrice ;
> }
> 
> int main()
> {
> 	CCaculateGoods s ;
> 	s.Input() ;
> 	printf("%d\n",s.Solve()) ;
> 	return 0 ;
> }

Home Page Go Back To top