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

hdu1176免费馅饼&&hdu2571命运 经典DP

 
阅读更多

hdu1176免费馅饼

比较无语的一个题、、、、、、、、、、

题意:gameboy每秒仅能移动一米,馅饼落在0-10m范围内,求能捡到的最多馅饼数。

写了个常规的DP动态方程,改来改去还是Time Limited Exceed 伤心呀 ~~~~然而的然而,学习了一下qsort的cmp函数写法。

对于结构体比较函数,写法为:t从小打到排列,x从大到小排列

int compare(const void *a,const void *b)//参数必须写成这个形式
{
	struct info *c=(info *)a;
	struct info *d=(info *)b;
	if(c->t!=d->t) return c->t-d->t;
	else return d->x-c->x;
}

言归正传,开始的思路是,开辟一个数组存放每个馅饼的掉落信息(悲剧就是这么发生的,唉~~).对馅饼的信息进行排序,时间小的在前,时间相等的坐标小的在前。

然后DP(该馅饼加上前面可达的馅饼中最多的馅饼数)、自认为思想很正确,但无疑不能AC,超时,尽管用了qsort。

额、、、比较难为情的是,我又看解题报告了尴尬(面壁思过了,已经).

这个题可以理解成数塔,看到这句话 我就看到了希望,是呀~~~~~巨轻松。。。。。

在这里我要警醒自己,换位思考、、、、、如果正着走不顺当,那就反过来走走试试 ,也许就是守得云开见月明啦

好啦 代码:

#include<string>
#include<stdio.h>
int num[100002][13];
int max(int a,int b,int c)
{
	if(a>=b&&a>=c) return a;
	else if(b>=a&&b>=c) return b;
	else return c;
}
int main()
{
	int n;
	while(scanf("%d",&n)&&n!=0)
	{
		memset(num,0,sizeof(num));
		int i=0,j;
		int x,t;
		int MaxT=0;
		for(;i<n;i++)
		{
			scanf("%d%d",&x,&t);
			num[t][x+1]++;
			if(MaxT<t) MaxT=t;
		}
		////从下向上DP。多美妙的思想吖
		for(i=MaxT-1;i>=0;i--)
		{
			for(j=11;j>0;j--)
			{
				num[i][j]+=max(num[i+1][j-1],num[i+1][j],num[i+1][j+1]);
			}
		}
		printf("%d\n",num[0][6]);
	}
	return 0;
}


hdu2571命运

经典的DP。

题意从1,1到达m,n点能途径的最大值。

注意初始化,有负值,所以初始化的时候要初始化为最小值-(m+n)*K=-102000;

对于DP[i][j],有三种到达方式:DP[i-1][j],DP[i][j-1],DP[i][k](k为j的因子)

代码:

#include<string>
#include<stdio.h>
int num[21][1005];
int sum[21][1002];
int max(int a,int b)
{
	return a>b?a:b;
}
int main()
{
	int m,t,n;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %d",&m,&n);
		int i=0,j,k;
		for(i=1;i<=m;i++)
		{
			for(j=1;j<=n;j++)
				scanf("%d",&num[i][j]);
		}
		for(int i=0;i<=m;i++) sum[i][0]=-1000000;  //***初始化       
		for(int j=0;j<=n;j++) sum[0][j]=-1000000;//****初始化
		sum[1][0]=0;sum[0][1]=0;//1,1点不需要最小值
		int mm;
		for(i=1;i<=m;i++)
		{
			for(j=1;j<=n;j++)
			{
				sum[i][j]=num[i][j];
				mm=max(sum[i-1][j],sum[i][j-1]);
				for(k=1;k<j;k++)
				{
					if(j%k==0&&mm<sum[i][k]) mm=sum[i][k];
				}
				sum[i][j]+=mm;
			}
		}
		printf("%d\n",sum[m][n]);
	}
	return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics