NYOJ 654 喜欢玩warcraft的ltl - c++编程基础

喜欢玩warcraft的ltl

时间限制：2000 ms | 内存限制：65535 KB 难度：3

描述

ltl 非常喜欢玩warcraft，因为warcraft十分讲究团队整体实力，而他自己现在也为升级而不拖累团队而努力。

他现在有很多个地点来选择去刷怪升级，但是在每一个地点他都要买上充足的补给和合适的道具，以免在刷怪的时候被怪物反杀了，每一个地点的怪物打完了就没有了（还居然不掉金钱跟装备），而且他只要选定了地点就一定会刷完该地点全部的怪物，同时获得对应的经验值。现在ltl 能给出每一个地点用来买补给和道具的钱和打完全部怪物所能获得的经验，但是他所拥有的钱是一定的。所以他想知道怎么选择地点使得他获得的经验最高。

输入

第一行一个整数T，表示测试数据的组数 0 第二行两个整数N,M，0 接下来N行每行两个整数ci,vi，(0 输出

一行一个整数，表示ltl能够获取的最大的经验值

样例输入

样例输出

Max experience: 12
Max experience: 6

读完题，立马断定01背包问题，然后直接写代码，不幸的是，TLE不期而至！

超时代码：

#include
       
        
struct node
{
	int c;
	int w;
}num[105];
int dp[1000005];
int Max(int a,int b)
{
	return a>b a:b;
}
int main()
{
	int T,n,m;
	int i,j;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		for(i=0;i
        
         =num[i].c;j--) { dp[j]=Max(dp[j],dp[j-num[i].c]+num[i].w); } } printf("Max experience: %d\n",dp[m]); } return 0; }
        
       

以下为优化代码：

#include
       
        
struct node
{
	int c;
	int w;
}num[105];
int dp[1000005];
int Max(int a,int b)
{
	return a>b a:b;
}
int main()
{
	int T,n,m;
	int i,j,s,count;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		s=0;
		for(i=0;i
        
         =count;j--) { dp[j]=Max(dp[j],dp[j-num[i].c]+num[i].w); } } printf("Max experience: %d\n",dp[m]); } return 0; }

点击复制链接与好友分享! 回本站首页

分享到：更多

您对本文章有什么意见或着疑问吗？请到论坛讨论您的关注和建议是我们前行的参考和动力

上一篇： hdu-3507-Print Article-斜率优化

下一篇： 最后一页

NYOJ 104 最大和和POJ 1050 To