首页 > 代码库 > HDU 1574 RP问题

HDU 1574 RP问题

2024-07-13 08:08:02   221人阅读

如果说难的话，难就难在对阶段的划分。

这又是一道对值域空间进行分段的题目。

因为rp有正有负，所以将整个数组向右平移10000个单位长度

l和r分别是rp可能的最小值

因为b是“门槛”，所以如果

发生好事（即c>0）循环就从b到r

发生坏事（即c<0）循环从l到b

然后从左到右找出最大值即可

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 const int INF = -999999; 9 const int maxn = 20000 + 10;10 int rp[maxn];11 12 int main(void)13 {14     #ifdef LOCAL15         freopen("1574in.txt", "r", stdin);16     #endif17 18     int N;19     scanf("%d", &N);20     while(N--)21     {22         int n;23         scanf("%d", &n);24         for(int i = 0; i < maxn; ++i)25             rp[i] = INF;26         int l, r;27         l = r = 10000;28         rp[l] = 0;29 30         while(n--)31         {32             int a, b, c;33             scanf("%d%d%d", &a, &b, &c);34             b += 10000;35             36             if(a < 0)37             {38                 for(int i = b; i <= r; ++i)39                     rp[i+a] = max(rp[i+a], rp[i]+c);40                 l += a;41             }    42             else43             {44                 for(int i = b; i >= l; --i)45                     rp[i+a] = max(rp[i+a], rp[i]+c);46                 r += a;47             }48         }49         int ans = 0;50         for(int i = l; i <= r; ++i)51             ans = max(ans, rp[i]);52         printf("%d\n", ans);53     }54     return 0;55 }
代码君


联系
我们