洛谷 P10884 [COCI 2017/2018 #2] San

思路

强力的剪枝。

大概就是这么几个数组：

• \(misum_i\)：表示从第 \(i\) 座楼出发，往后跳能拿到的最大金币总和。
• \(num_i\)：表示从第 \(i\) 座楼出发，往后跳的所有可能的方案数。

预处理很简单，剪枝也不难，按照逻辑，可行性剪枝即可

代码

码风极其丑陋，勿喷。

//dfs+剪枝
int dfs(int w,int s){
    int res=0;
	if(s+g[w]>=k)return num[w];
	if(k-s>misum[w])return 0;
	for(int i=w+1;i<=n;i++)
		if(h[i]>=h[w])
            res+=dfs(i,s+g[w]);
	return res;
}

//预处理
for(int i=n;i>=0;i--){
    num[i]=1;
    for(int j=n;j>i;j--)
			if(h[j]>=h[i]){ 
				misum[i]=max(misum[i],misum[j]);
				num[i]+=num[j];
			}
		misum[i]+=g[i];
	}

//输出
cout<<dfs(0,0);