P3252 [JLOI2012]树

123

<span id="Label3">标签：节点 jloi2012 方案 时间复杂度 amp 时间 int target space
Aimee
记忆化搜索非常好写,
尤其是从一个朴素的搜索开始改造。
sum是要记录的，但是没必要存在状态里
直接统计一下当前节点是第几步之后的方案数
虽然说时间复杂度没有朴素的优美
但是不会MLE啊
#include#include#include#include#define int long longusing namespace std;int n,s;int Aimee[100001];int x,y;int head[100001];int dp[101][100001];struct b{        int to;        int ne;}b[100001];int p;int ans;void add(int f,int to){        p++;        b[p].ne=head[f];        b[p].to=to;        head[f]=p;        return ;}int dfs(int now,int de,int sum){        if(dp[de][now]) return dp[de][now];        sum+=Aimee[now];        if(sum>s)        return 0;        if(sum==s)        return dp[de][now]=1;        int res=0;        for(int i=head[now];i;i=b[i].ne){        res+=dfs(b[i].to,de+1,sum);        }        return dp[de][now]=res;}signed main(){        scanf("%lld%lld",&n,&s);        for(int i=1;i

鬧夠了就去吃藥

沙发？？？

乐果o

楼下的接上

天生我才屌炸天

我也顶起出售广告位

不明爬行物

沙发？？？

可爱到不行

楼主呀，，，您太有才了。。。

钱包你瘦了

……

期中你好吊

支持楼主，用户楼主，楼主英明呀！！！

逗爷！

打酱油的人拉，回复下赚取积分

撸代码

广告位，，坐下看看