#C240128B. 挖煤(coal)

标签（Label）

• 动态规划
• 逆向思维

前言（Front talk)

这道题的逆向思维非常的聪明，思维触发点在于前面的对后面的有影响，而后面的对前面的没有影响。

网址（Website）

#C240128B. 挖煤(coal) - 洛谷

题解（Solution）

看到这道题的第一感觉——这道题很像 $dp$ ，然后发现 $dp$ 好像做不出来。

这道题从正向的方面很难入手，因为当前的每一个操作都会对后面有影响，暴力枚举的话时间复杂度是 $O(2^n)$ ，但是可以进行一些小小的优化。因为对于同一位置的任意两个状态（每个状态对应钱数 $mon$ 和魔力值 $mag$），当有 $mon_1\le mon_2$ 且 $mag1\le mag2$ 时，状态 $mon_1,mag_1$ 一定不是最优的。然后我想到用 $set$ 维护这两个键值，每次暴力枚举煤矿或补给点后，就遍历一遍 $set$ ，删除不必要的状态。

这样可以得 $60pts$ 。

正解，则是直接倒序动态规划即可，此处略去。

代码（Code）

$60pts$

#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;
}

$100pts$

#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;
}