Description
　　張遼是一個長發飄飄的非常聰明的男孩，人人都稱他為“遼哥”。遼哥喜歡玩一個有趣的電腦游戲。這個游戲開始的時候有n個碉堡，每個碉堡擁有一個防御值和一個附加值。玩家擁有一個初始的攻擊力。如果玩家破壞了一個碉堡，則他能得到1分。每一次，遼哥會選擇一個碉堡進行攻擊。所有未被破壞的碉堡會聯合起來防御，因此為了破壞那個碉堡，遼哥的攻擊力必須大于或者等于所有未被破壞的碉堡的防御值之和，否則遼哥就會輸掉游戲。如果遼哥成功破壞了那個碉堡，那么他的攻擊力會變成那個碉堡的附加值，然后他可以選擇下一個攻擊的目標。
　　由于遼哥擁有強大的編程能力，他不費吹灰之力就改寫了那個游戲。在游戲開始前，他可以用炸彈消滅任意的碉堡，但是他不能通過這種方式來獲得分數。問題來了，在游戲開始后，遼哥可以得到的最大分數是多少？

Input
　　輸入包含多組（不超過100組）測試數據。
　　每組測試數據的第一行包含一個正整數N，表示測碉堡的數目。接下來有N行，每行包括2個非負整數。第i+1行的2個整數分別表示第i個碉堡的防御值和附加值。最后還有一行，為一個整數，表示遼哥在游戲開始時的初始攻擊力。
　　輸入以文件結束符結束。

Output
　　對每組數據，輸出一行，為一個整數，表示遼哥可以拿到的最大分數。

Sample Input
3
10 9
25 30
8 7
50
5
100 230
334 331
33 288
35 100
334 22
600

Sample Output
3
4

Data Constraint

Hint
【數據范圍】
　　對20%的數據，有N<=10；
　　對40%的數據，有N<=100；
　　對100%的數據，有N<=1000，每個碉堡的防御值和附加值均不會超過2000000。

.
.
.
.
.
分析
開始時將若干個碉堡炸掉的操作有點難處理，我們考慮倒著做。
設 f[i] 表示選的最后 i 個碉堡（任意選）的所需的最小攻擊力。
設第 j個碉堡的防御值和附加值分別為 b[j],d[j] ，
則有 f[i]=min{f[i?1]+b[j]} (d[j]≥f[i?1])。
還有碉堡要按 b+d從小到大排序（顯然 b+d小的后選更優）。
這樣處理完之后選一個最大的 f[i] 使得初始攻擊力 m≥f[i]即滿足題意，輸出此時的 i即可。
時間復雜度 O(T?n*n)。

.
.
.
.
.
程序：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std;int n,f[2000];struct edge {int x,y; }a[2000];inline int read() {int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w; }bool cmp(edge x,edge y) {return x.x+x.y<y.x+y.y; }int main() {while (scanf("%d",&n)!=EOF){for (int i=1;i<=n;i++) {a[i].x=read();a[i].y=read();} memset(f,0X3f,sizeof(f));sort(a+1,a+1+n,cmp);f[0]=0;for (int i=1;i<=n;i++)for (int j=i;j>=1;j--)if (a[i].y>=f[j-1]) f[j]=min(f[j],f[j-1]+a[i].x);for (int i=n,m=read();i>=0;i--)if (m>=f[i]){printf("%d\n",i);break;}}return 0; }

轉載于:https://www.cnblogs.com/YYC-0304/p/11094929.html

總結

以上是生活随笔為你收集整理的辽哥游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。