Description

Input

Output

Sample Input

5 50 50 10
1 10
1 20
2 10
2 20
1 30

Sample Output

375.00

Data Constraint

Solution

• 本題最大的瓶頸在于“當前鉆頭能力”，我們嘗試不儲存“當前鉆頭能力”。

• F[i] 表示前 i 個星球的最優收入。但這很明顯是不行的，因為當前鉆頭能力會影響到后面的過程。

• 不嚴謹的說，當前鉆頭能力具有“后效性”。

• 但是這個當前鉆頭能力對后程的影響無非就是乘上一個數值。

• 就好像初始鉆頭能力是 w ，實際上你可以按 1 來做，最后再把 ans 乘上 w 。

• 正難則反 ，F[i] 表示第 i——n 個星球的最優收入，且假設從第 i 個星球開始時鉆頭能力是 1 。

• 轉移過程就變得簡單：

• 如果在第 i 個星球開采，那么第 i——n 個星球的初始鉆頭能力就是 1?(1?0.01?k) 。

• 換句話說，就是：F[i+1]?(1?0.01k) 。所以：

  F[i]=Max{F[i+1],F[i+1]?(1?0.01k)+a[i]}

• 對于維護型星球，大同小異，就系數和代價的正負而已。

• 實際處理時數組也不用，用變量存儲即可，時間復雜度 O(N) 。

Code

#include<cstdio> using namespace std; const int N=100001; double ans; int a[N]; bool b[N]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline double max(double x,double y) {return x>y?x:y; } int main() {int n=read();double k=read(),c=read(),w=read();k=1-0.01*k,c=1+0.01*c;for(int i=1;i<=n;i++) b[i]=read()==1,a[i]=read();for(int i=n;i;i--) ans=max(ans,b[i]?ans*k+a[i]:ans*c-a[i]);printf("%.2lf",ans*w);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 5377. 【NOIP2017提高A组模拟9.19】开拓的全部內容，希望文章能夠幫你解決所遇到的問題。

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