【題目描述】

寵物小精靈是一部講述小智和他的搭檔皮卡丘一起冒險的故事。

一天，小智和皮卡丘來到了小精靈狩獵場，里面有很多珍貴的野生寵物小精靈。小智也想收服其中的一些小精靈。然而，野生的小精靈并不那么容易被收服。對于每一個野生小精靈而言，小智可能需要使用很多個精靈球才能收服它，而在收服過程中，野生小精靈也會對皮卡丘造成一定的傷害（從而減少皮卡丘的體力）。當(dāng)皮卡丘的體力小于等于0時，小智就必須結(jié)束狩獵（因為他需要給皮卡丘療傷），而使得皮卡丘體力小于等于0的野生小精靈也不會被小智收服。當(dāng)小智的精靈球用完時，狩獵也宣告結(jié)束。

我們假設(shè)小智遇到野生小精靈時有兩個選擇：收服它，或者離開它。如果小智選擇了收服，那么一定會扔出能夠收服該小精靈的精靈球，而皮卡丘也一定會受到相應(yīng)的傷害；如果選擇離開它，那么小智不會損失精靈球，皮卡丘也不會損失體力。

小智的目標(biāo)有兩個：主要目標(biāo)是收服盡可能多的野生小精靈；如果可以收服的小精靈數(shù)量一樣，小智希望皮卡丘受到的傷害越小（剩余體力越大），因為他們還要繼續(xù)冒險。

現(xiàn)在已知小智的精靈球數(shù)量和皮卡丘的初始體力，已知每一個小精靈需要的用于收服的精靈球數(shù)目和它在被收服過程中會對皮卡丘造成的傷害數(shù)目。請問，小智該如何選擇收服哪些小精靈以達到他的目標(biāo)呢？

【輸入】

輸入數(shù)據(jù)的第一行包含三個整數(shù)：N(0<N<1000)，M(0<M<500)，K(0<K<100)，分別代表小智的精靈球數(shù)量、皮卡丘初始的體力值、野生小精靈的數(shù)量。

之后的K行，每一行代表一個野生小精靈，包括兩個整數(shù)：收服該小精靈需要的精靈球的數(shù)量，以及收服過程中對皮卡丘造成的傷害。

【輸出】

輸出為一行，包含兩個整數(shù)：C，R，分別表示最多收服C個小精靈，以及收服C個小精靈時皮卡丘的剩余體力值最多為R。

【輸入樣例】

10 100 5
7 10
2 40
2 50
1 20
4 20

【輸出樣例】

3 30

【源程序】

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<string> #include<cstdlib> #include<queue> #include<vector> #define INF 0x3f3f3f3f #define PI acos(-1.0) #define N 1001 #define MOD 2520 #define E 1e-12 using namespace std; int V,U,n; int v[N],u[N],f[N][N]; void TwoDimensionPack(int weight_1,int weight_2) {for(int j=V;j>=weight_1;j--)for(int k=U;k>=weight_2;k--)f[j][k]=max(f[j][k],f[j-weight_1][k-weight_2]+1); } int main() {cin>>V>>U>>n;for(int i=1;i<=n;i++)cin>>v[i]>>u[i];for(int i=0;i<=V;i++)//邊界設(shè)定for(int j=0;j<=U;j++)f[i][j]=0;for(int i=1;i<=n;i++)TwoDimensionPack(v[i],u[i]);int cnt=0;for(int i=1;i<=U;i++){if(f[V][i]==f[V][U]){cnt=i;break;}}cout<<f[V][U]<<" "<<U-cnt<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的宠物小精灵之收服（信息学奥赛一本通-T1292）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。