`
java-mans
  • 浏览: 11339630 次
文章分类
社区版块
存档分类
最新评论

hdu1160&&1087

 
阅读更多

很久没写DP了(大概一年之久),由此可鉴,没有付出足够的努力呀

在思考过程中一直警醒自己 不能看解题报告,于是乎,艰苦的独立完成了,虽然是俩简单的DP,但收获不小,吼吼~~~~~~

Super Jumping! Jumping! Jumping!

这个题意是,一维空间上求和最大的一个可以不连续的序列,输出最大和。

推导DP的动态方程时,只需要找比当前值小的和的最大值加上当前的值,即为当前值的最大和,记录整个搜索过程中的最大和即为所求。

该题需要注意的是,Max值会超出int范围。

DP方程式为:

DP[i]=num[i]+max(DP[i-1,i-2....0]);

做题的时候一直WA,原因是,DP方程有误,max(DP[i-1,i-2....0]),误写成最接近当前num的DP。没有注意到最接近的不一定是和最大的。

如果求最大连续序列的和(有负值),输出开始点,结束点。只需要记录并修改begin值(和小于0时)和end值(和大于当前最大和时)即可。

FatMouse's Speed

题意,weight严格递增,speed严格递减的Mice序列。

分析,可以借助sort对speed或者weight排序(记录Mice的编号)然后对另外一个属性,求单调递增子序列。并输出该序列及序列长度

找每个Mice的weight或speed比自己小的值的最大值,DP更新为 当前Mice应有的顺序号。记录整个DP过程中最大的排序号。

DP完毕倒序查找一个序列。

1160的代码:

#include<iostream>
using namespace std;
int num[1001];
long long dp[1001];
int main()
{
	int n,i;
	while (cin>>n&&n)
	{
		long long mx;
		cin>>num[1];
		dp[0]=0;
		dp[1]=num[1];
		mx=dp[1];
		for(i=2;i<=n;i++)//DP过程
		{
			cin>>num[i];
			long long mn=0;
			for(int j=i-1;j>0;j--)
			{
				if(num[i]>num[j])
				{
					if(dp[j]>mn)
						mn=dp[j];
				}
			}
			dp[i]=num[i]+mn;
			if(mx<dp[i]) mx=dp[i];
		}
		cout<<mx<<endl;
	}
	return 0;
}


1087的代码:

#include<iostream>
#include<algorithm>
using namespace std;
struct info
{
	int w;
	int s;
	int f;
}Mice[1001];
bool compare(struct info a,struct info b)
{
	if(a.s>b.s) return 1;
	else if((a.s==b.s)&&(a.w<b.w)) return 1;
	else return 0;
}
int max(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	int m,n;
	int k=1;
	while(cin>>m>>n)
	{
		Mice[k].w=m;
		Mice[k].s=n;
		Mice[k].f=k++;
	}
	sort(Mice,Mice+k,compare);
	int i,j;
	int len=0;
	Mice[0].s=0;
	for(i=1;i<k-1;i++)
	{
		Mice[i].s=0;
		for(j=0;j<i;j++)
		{
			if(Mice[i].w>Mice[j].w) Mice[i].s=max(Mice[i].s,Mice[j].s+1);
		}
		if(len<Mice[i].s) len=Mice[i].s;
	}
	cout<<len+1<<endl;
	int flag=k-1;//标记当前最大值的位置
	int num[1001];
	//从后向前找,从大到小找,然后倒序输出
	for(i=len;i>=0;i--)
	{
		for(j=flag-1;j>=0;j--)
			if(Mice[j].s==i) {num[i]=j;flag=j;break;}
	}
	for(i=0;i<=len;i++)//到序输出

	{
		cout<<Mice[num[i]].f<<endl;
	}
	return 0;
}
收获:

做DP的时候,观察DP的最终结果与前n项的联系,找出动态转移方程,从而求解。

另:愿姐姐生日快乐,3.8节快乐

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics