#C240128B. 挖煤(coal)
前言(Front talk)
这道题的逆向思维非常的聪明,思维触发点在于前面的对后面的有影响,而后面的对前面的没有影响。
网址(Website)
题解(Solution)
代码(Code)
#include<bits/stdc++.h>
#include<set>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<double,double>
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 101234;
int op[N],a[N];
int n,k,c,w;
double ans;
set<P> s[2],cmp;
void Init(){cin>>n>>k>>c>>w;For(i,1,n) cin>>op[i]>>a[i];}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
string str("coal");
freopen((str+".in").c_str(),"r",stdin);
freopen((str+".out").c_str(),"w",stdout);
Init();double Tim=clock();
s[1].emplace(w,0);
For(i,1,n){
int p=i&1;s[p^1]=s[p];
for(auto kk:s[p]){
double mag=kk.first,mon=kk.second;
if(op[i]==1) s[p^1].emplace(mag*(1-k/100.),mon+mag*a[i]);
if(op[i]==2) s[p^1].emplace(mag*(1+c/100.),mon-mag*a[i]);
}s[p]=s[p^1];
for(auto ii=s[p].begin(),jj=s[p].begin();jj!=s[p].end();ii++,jj++){
if(jj==s[p].begin()) jj++;
if(ii->first<=jj->first && ii->second<=jj->second)
s[p^1].erase(make_pair(ii->first,ii->second));
}
}for(auto kk:s[n&1]) ans=max(ans,kk.second);
for(auto kk:s[(n&1)^1]) cerr<<kk.first<<' '<<kk.second<<'\n';
cerr<<"Size:"<<s[(n&1)^1].size()<<'\n';
printf("%.2lf\n",ans);
return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}
#include<bits/stdc++.h>
#include<set>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<double,double>
#define int long long
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 101234;
int op[N],a[N];
int n;
double k,c,w;
double ans,f[N];
void Init(){cin>>n>>k>>c>>w;For(i,1,n) cin>>op[i]>>a[i];}
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
string str("coal");
freopen((str+".in").c_str(),"r",stdin);
freopen((str+".out").c_str(),"w",stdout);
Init();double Tim=clock();
k/=100.,c/=100.;
Rof(i,n,1){
if(op[i]==1) f[i]=max(f[i+1],f[i+1]*(1-k)+a[i]);
if(op[i]==2) f[i]=max(f[i+1],f[i+1]*(1+c)-a[i]);
}printf("%.2lf\n",f[1]*w);
return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}