RP問題

Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)

Problem Description 在人類社會中，任何個體都具有人品，人品有各種不同的形式，可以從一種形式轉換為另一種形式，從一個個體傳遞給另一個個體，在轉換和傳遞的過程中，人品不會消失，也不被能創造，這就是，人品守恒定律！
人品守恒定律更形象的描述，當發生一件好事，你從中獲利，必定消耗一定量RP；當發生一件不幸的事，你在其中有所損失，必定積攢一定量RP。
假設在一個時間段內在你身上可能會發生N個事件，每個事件都對應一個RP變化值a、RP門檻值b和獲益值c。當RP變化值a為正，獲益值c必定為負，只有你當前的RP值小于等于RP門檻值b的時候，此事件才有可能發生，當此事件發生時，你的RP值將增加|a|，獲益值將減少|c|。反之，當RP變化值a為負，獲益值c必定為正，只有你當前的RP值大于等于RP門檻值b的時候，此事件才有可能發生，當此事件發生時，你的RP值將減少|a|，獲益值將增加|c|。
一個事件在滿足上述RP條件的前提下，未必會發生。假設在這段時間之前你所具有的RP值和獲益值都為0，那么過了這段時間后，你可能達到的最大獲益值是多少？
注意：一個人的所具有的RP值可能為負。

Input 輸入數據的第一行為一個正整數T，表示有T組測試數據。每組測試數據的第一行為一個正整數N (0 < N <= 1000)，表示這個時間段在你身上可能發生N個事件。接下來N行，每行有三個整數a, b, c (0 <= |a| <= 10, 0 <= |b| <= 10000, 0 <= |c| <= 10000)。這N個事件是按照輸入先后順序先后發生的。也就是說不可能先發生第i行的事件，然后再發生i – j行的事件。
Output 對應每一組輸入，在獨立一行中輸出一個正整數，表示最大可能獲益值。
Sample Input 3 1 -1 0 1 2 10 200 -1 -5 8 3 3 -5 0 4 10 -5 -5 -5 5 10
Sample Output 1 2 9
解題思路：這道題由于RP可以為負的，所以可以加偏移量用數組保存，dp[i]表示RP為i時最大獲利。這里由于a的正負會影響當前RP值和b的關系，所以a要分情況討論，剩下的就是01背包了。注意最開始dp[]要賦值負無窮。
#include<iostream> #include<cstdio> #include<cstring> using namespace std;const int maxn = 20001; const int inf = 0x7fffff; int n,dp[maxn];int main() {int t,a,b,c;scanf("%d",&t);while(t--){for(int i = 0; i <= 20000; i++) dp[i] = -inf;scanf("%d",&n);dp[10000] = 0;for(int i = 1; i <= n; i++){scanf("%d%d%d",&a,&b,&c);if(a > 0){for(int j = 10000+b; j >= 0; j--)dp[j+a] = max(dp[j+a],dp[j]+c);}else {for(int j = 10000+b; j <= 20000; j++)dp[j+a] = max(dp[j+a],dp[j]+c);}}int ans = 0;for(int i = 0; i <= 20000; i++)ans = max(ans,dp[i]);printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu 1574(01背包)的全部內容，希望文章能夠幫你解決所遇到的問題。

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