a problem solved by dynamic programming and some ideals

编程知识 更新时间:2023-04-03 18:25:42

Hello,everyone. Today is the second day,and i am fighting.You must know that dynamic programming is a flexible problem.And there is a ad problem.You want to make ad walls on a street to earn money.But each two of them can not be close as 5.And different ad walls can only be placed at the fixed place,and they have different values.To be honest,the length of the street is not useful.Because i just want to know how to set the walls.So the point is the walls.And it should be the only variable.So the real point should be the variable.

Have fun coding,i_human.Have fun coding,everyone!


THE CODE:


// 广告牌树立问题.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
#define a 100

using namespace std;

int get(int j);

int b[2][a];
int c[a];
int d[a];

int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		d[i]=-1;
	for(int i=1;i<=n;i++)
		c[i]=-1;
	for(int i=1;i<=n;i++)
	{
		cin>>b[0][i]>>b[1][i];
		for(int j=1;j<=i;j++)
		{
			if(b[0][j]+5<b[0][i])
				c[i]=j;
		}
		if(c[i]==-1)
			c[i]=0;
	}
	cout<<get(n)<<endl;
	system("pause");
	return 0;
}

int get(int n)
{
	if(d[n]!=-1)
		return d[n];
	if(c[n]==0)
		return b[1][n];
	if(get(n-1)>=get(c[n])+b[1][n])
	{
		d[n]=get(n-1);
		return d[n];
	}
	if(get(n-1)<get(c[n])+b[1][n])
	{
		d[n]=get(c[n])+b[1][n];
		return d[n];
	}
}


更多推荐

a problem solved by dynamic programming and some ideals

本文发布于:2023-04-03 18:25:00,感谢您对本站的认可!
本文链接:https://www.elefans.com/category/jswz/ce64fe7f7a77afc53172583c1d5a2933.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文标签:solved   problem   dynamic   ideals   programming

发布评论

评论列表 (有 0 条评论)
草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍!

  • 39475文章数
  • 14阅读数
  • 0评论数