NYOJ 654 喜歡玩warcraft的ltl

喜歡玩warcraft的ltl

描述

ltl 非常喜歡玩warcraft，因為warcraft十分講究團隊整體實力，而他自己現在也為升級而不拖累團隊而努力。

他現在有很多個地點來選擇去刷怪升級，但是在每一個地點他都要買上充足的補給和合適的道具，以免在刷怪的時候被怪物反殺了，每一個地點的怪物打完了就沒有了（還居然不掉金錢跟裝備），而且他只要選定了地點就一定會刷完該地點全部的怪物，同時獲得對應的經驗值。現在ltl 能給出每一個地點用來買補給和道具的錢和打完全部怪物所能獲得的經驗，但是他所擁有的錢是一定的。所以他想知道怎麼選擇地點使得他獲得的經驗最高。

輸入

第一行一個整數T，表示測試數據的組數 0 第二行兩個整數N,M，0 接下來N行每行兩個整數ci,vi，(0 輸出

一行一個整數，表示ltl能夠獲取的最大的經驗值

樣例輸入

2
3 10
7 7
2 3
3 5
2 5
3 5
2 1

樣例輸出

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;
}