題目連結：https://vjudge.net/problem/CodeForces-922E
E. Birds time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output
Apart from plush toys, Imp is a huge fan of little yellow birds!
To summon birds, Imp needs strong magic. There are n trees in a row on an alley in a park, there is a nest on each of the trees. In the i-th nest there are ci birds; to summon one bird from this nest Imp needs to stay under this tree and it costs him costi points of mana. However, for each bird summoned, Imp increases his mana capacity by B points. Imp summons birds one by one, he can summon any number from 0 to ci birds from the i-th nest.
Initially Imp stands under the first tree and has W points of mana, and his mana capacity equals W as well. He can only go forward, and each time he moves from a tree to the next one, he restores X points of mana (but it can't exceed his current mana capacity). Moving only forward, what is the maximum number of birds Imp can summon?
Input
The first line contains four integers n, W, B, X (1 ≤ n ≤ 103, 0 ≤ W, B, X ≤ 109) — the number of trees, the initial points of mana, the number of points the mana capacity increases after a bird is summoned, and the number of points restored when Imp moves from a tree to the next one.
The second line contains n integers c1, c2, ..., cn (0 ≤ ci ≤ 104) — where ci is the number of birds living in the i-th nest. It is guaranteed that
.
The third line contains n integers cost1, cost2, ..., costn (0 ≤ costi ≤ 109), where costi is the mana cost to summon a bird from the i-th nest.
Output
Print a single integer — the maximum number of birds Imp can summon.
Examples input Copy
2 12 0 4
3 4
4 2 output
6 input Copy
4 1000 10 35
1 2 4 5
1000 500 250 200 output
5 input Copy
2 10 7 11
2 10
6 1 output
11 Note
In the first sample base amount of Imp's mana is equal to 12 (with maximum capacity also equal to 12). After he summons two birds from the first nest, he loses 8 mana points, although his maximum capacity will not increase (since B = 0). After this step his mana will be 4 of 12; during the move you will replenish 4 mana points, and hence own 8 mana out of 12 possible. Now it's optimal to take 4 birds from the second nest and spend 8 mana. The final answer will be — 6.
In the second sample the base amount of mana is equal to 1000. The right choice will be to simply pick all birds from the last nest. Note that Imp's mana doesn't restore while moving because it's initially full.
題意：
有n棵樹，在第i棵樹上有ci隻小鳥，在此樹召喚一隻小鳥需要花費costi個mama，但卻能增加b個機關裝mama的容量。人初始時在第一棵樹下，且隻能往前走，但每往前走一棵樹，就能得到x個mama，前提是不能超過容量，初始容量和mama值都為w。問在第n棵樹時，最多能召喚多少隻小鳥。
題解：
1.一看題目，就很容易想到DP遞推：設 dp[i][cnt]為到達第i棵樹，且剩餘cnt個mama的情況下，最多能召喚多少隻小鳥。
2.但是，在看看資料：w、cost等有關mama的大小範圍都為：1e9，數組根本開不了這麼大。而卻規定了：
，多麼（找不到形容詞）。
3.根據資料範圍，重新調整一下dp數組，設dp[i][j]為：到達第i棵樹，且召喚了j隻小鳥所剩下的mama的最大值。
4.那麼就可以根據此遞推。
代碼如下：
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <algorithm>
5 #include <vector>
6 #include <cmath>
7 #include <queue>
8 #include <stack>
9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const int INF = 2e9;
15 const LL LNF = 9e18;
16 const int MOD = 1e9+7;
17 const int MAXN = 1e5+10;
18
19 LL dp[2][10010]; //直接開1e3*1e4，記憶體開銷太大，故使用滾動數組
20 int c[1010], cost[1010];
21 int main()
22 {
23 int n, w, b, x;
24 while(scanf("%d%d%d%d", &n,&w,&b,&x)!=EOF)
25 {
26 int sum = 0;
27 for(int i = 1; i<=n; i++) scanf("%d", &c[i]), sum += c[i];
28 for(int i = 1; i<=n; i++) scanf("%d", &cost[i]);
29
30 memset(dp, -1, sizeof(dp));
31 for(int j = 0; j<=c[1]; j++) //初始化第一棵樹
32 dp[1][j] = 1LL*w-1LL*j*cost[1];
33 for(int i = 2; i<=n; i++)
34 {
35 memset(dp[i&1], -1, sizeof(dp[i&1])); //記得初始化
36 for(int j = 0; j<=sum; j++)
37 {
38 for(int k = 0; k<=min(j,c[i]); k++)
39 {
40 //小于0，即不可能達到的狀态，必須退出。否則往後可能又會變成正，認為此狀态是存在的，對答案有影響。
41 if(dp[(i-1)&1][j-k]<0) continue;
42 LL tmp = min(1LL*w+1LL*(j-k)*b, dp[(i-1)&1][j-k]+x)-1LL*k*cost[i];
43 dp[i&1][j] = (dp[i&1][j]==-1)?tmp:max(dp[i&1][j],tmp);
44 }
45 }
46 }
47
48 int cnt = sum;
49 while(cnt && dp[n&1][cnt]<0) cnt--;
50 printf("%d\n", cnt);
51 }
52 } View Code
轉載于:https://www.cnblogs.com/DOLFAMINGO/p/8598417.html