伪紫题p5194 天平（dfs剪枝）

这题作为一个紫题实在是过分了吧。。。
绿的了不起了。
——————————————————————————

看题第一眼，01背包无误。2min打好一交全屏紫色（所以这就是这题是紫色的原因233？）

re原因：即使压掉一维，dp数组的下标也有1e10 * 2 以上，不MLE就不错了。

肯定是动态规划一类的东西了。根据题目这一句话：这一行中从第3个砝码开始，每个砝码的质量至少等于前面两个砝码（也就是质量比它小的砝码中
质量最大的两个）的质量的和。是不是很像斐波那契？于是推出来：n的真实值其实也很小，大约在30左右吧。但是朴素搜索也会原地爆裂。

怎么剪枝呢？大约有三个剪枝。

#1：输入的时候，如果当前的重量已经大于限制了，就停止，把砝码总数重新定义。

#2：题目里所有的砝码都是单调递增的，所以不会出现去掉前面某一个砝码然后取后面一个来找到最大值（可能表述有些问题，或者我根本理解错了，欢迎指正）所以维护一个前缀和，如果这个能拿，就把前面的全都拿了（或者说当前的砝码一定大于等于前面所有的砝码重量和）

#3:因为找最大，所以从后往前搜索。

大概就是这样。

#include<bits/stdc++.h>

//变量解释：a数组存题目给定值，b数组为前缀和数组，n为砝码数量，m为限制重量

using namespace std;

const int maxn=500005;

int n,m;

long long ans,a[maxn],b[maxn];

void dfs(int now,long long ma)//当前砝码序号和最大值

{

　　if(ma+b[now]<=ans)//剪枝#2

　　return;

　　ans=max(ans,ma);

　　for(int i=now;i;i--)//剪枝#3

　　if(ma+a[i]<=m)

　　dfs(i-1,ma+a[i]);

}

int main()
{

　　scanf("%d%d",&n,&m);

　　for(int i=1;i<=n;i++)

　　{

　　　　scanf("%lld",&a[i]);

　　　　if(a[i]>m)

　　　　{

　　　　　　n=i-1;//剪枝#1

　　　　　　break;

　　　　}

　　　　b[i]=b[i-1]+a[i];//剪枝#2

　　}

　　dfs(n,0);

　　printf("%lld",ans);

　　return 0;

}

应该就是这样吧。。。
（完）

巴特西

伪紫题p5194 天平（dfs剪枝）

最新文章

热门文章