HDOJ FATE 二維DP

一道很水的二維DP，但是對于DP沒有什麼感覺的我來說，真是辛苦了。

這麼來。[疲勞值][怪物數量]=經驗值。這樣儲存的目前疲勞值擷取的最大經驗者。

dp[i][j]=max( dp[i][j],dp[i-m_pl[k]][j-1]+m_exp[k] );

當經驗值滿足更新的條件就可以了。

#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;

int max( int a,int b ){ return a>b?a:b; }

int main()
{
 	int exp,pl,n,maxn;
 	int dp[111][111];
 	int mexp[111],mpl[111];
 	while( scanf( "%d%d%d%d",&exp,&pl,&n,&maxn )!=EOF )
 	{
	 	   memset( dp,0,sizeof(dp) );
	 	   
	 	   for( int i=1;i<=n;i++ )
	 	   		scanf( "%d%d",&mexp[i],&mpl[i] );
	 	   
	 	   int i;
		   for( i=1;i<=pl;i++ )
		   {
	 	   		for( int j=1;j<=maxn;j++ )
	 	   		for( int k=1;k<=n;k++ )
	 	   		 	 if( i>=mpl[k] )
	 	   			 	 dp[i][j]=max( dp[i][j],dp[i-mpl[k]][j-1]+mexp[k] );
				if( dp[i][maxn]>=exp )
	 	   			break;
		   }
		   
	 	   printf( "%d\n",pl-i );
  	}
 	return 0;
}