洛谷 P1156 垃圾陷阱谈论剪枝，非满分

这是一个91分的非dp代码（是我太弱）

剪枝八五个（实际上根本没那么多，主要是上课装逼，没想到他们dp水过去了），不过我的思路与dp不同；

1.层数到达i+1,return 这个必须有

2.当前剩余生命吃不到垃圾，return，必须有

3.当前答案比目前最优解大，return

4.到达第i个点，剩余相同的生命，但是比以前走的短，return

5.到达第t时间，剩余相同生命，同上return

6.增加一个上限阀值，这样目前的解很接近最正确答案（但是第二和5个数据点貌似专门在卡这个（是我太弱）

7.做两次dfs，第一次先贪存货时间久，第二次贪升高（玄学的是如果调换就会只有45）

~~8.烧香~~

尤其要注意的是，这道题并没有保证输入数据按从小到大来，因此你还需要对输入的数据排遍序！

代码一：

 #include<iostream>

 #include<queue>

 #include<cstring>

 #include<algorithm>

 #include<fstream>

 using namespace std;

 int life=;

 int d1[][],d2[][];  //d1指的是

 int n,d;

 struct junk{

     int h,t,l;

 };

 int cmp(junk a,junk b)

 {

     return a.t<b.t;

 }

 int ans=0x3ffffff;

     int lifenow=;

 int ts=;

 junk f[];

 int bj(int t)

 {

     ans=min(ans,t);

     ts=;

 }

 int bj2(int l)

 {

     lifenow=max(l,lifenow);

 }

 long long u;

 long long p=0x2FFFFFF-;

 void dfs1(int i,int dep,int l,int t)

 {

     u++;

     if(u>p/) return ;

     bj2(l);

     if(t>ans) return ;

     if(l<f[i].t) return ;

     if(dep>=d)

     {

     bj(t);

     return ;

     }

     if(i>n) return ;

      if(d1[i][l]>dep||d2[t][l]>dep) return ;

     d1[i][l]=dep;

     d2[t][l]=dep;

     dfs1(i+,dep,l+f[i].l,f[i].t);

      dfs1(i+,dep+f[i].h,l,f[i].t);

      if(u>p/) return ;

 }

 void dfs2(int i,int dep,int l,int t)

 {

     u++;

     if(u>p) return ;

     bj2(l);

     if(t>ans) return ;

     if(l<f[i].t) return ;

     if(dep>=d)

     {

     bj(t);

     return ;

     }

     if(i>n) return ;

     if(d1[i][l]>dep||d2[t][l]>dep) return ;

     d1[i][l]=dep;

     d2[t][l]=dep;

     dfs2(i+,dep+f[i].h,l,f[i].t);

     dfs2(i+,dep,l+f[i].l,f[i].t);

      if(u>p) return ;

 }

 int main()

 {

     cin>>d>>n;

     int h=;

     int i,j,k;

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

     cin>>f[i].t>>f[i].l>>f[i].h;

     sort(f+,f+n+,cmp);

     dfs1(,,,);

     dfs2(,,,);

     if(ans==||lifenow==)

     {

         cout<<;

         return ;

     }//骗分

     if(ts)

     cout<<ans;

     else cout<<lifenow;

     return ;

 }

 /*

    \     |     /

     \    |    /

      \   |   /

       \  |  /

        \ | /

         \|/

       Accept!

       0ms/0kb

 */

另外，我们发现，dfs的复杂度太高主要是有太多次优借刷新，我们如果将d1,d2改变,让他变成每个点每种情况的的dfs到达次数，那么，我们可以通过来限制某个情况被刷新的次数来优化时间复杂度，假设每个点被限制t次，t是可以极小的，大约为100，(*1e7 / gt≈800)t=100时，时间大大优化了，可以自己去测一下,大约为15ms，比一般的dfs优化了不知道多少.(还是91分，不知道剩下那个数据有多毒瘤）

代码2：

#include<iostream>

#include<queue>

#include<cstring>

#include<algorithm>

#include<fstream>

using namespace std;

int life=;

int d1[][],d2[][];

int n,d;

struct junk{

    int h,t,l;

};

int cmp(junk a,junk b)

{

    return a.t<b.t;

}

int ans=0x3ffffff;

    int lifenow=;

int ts=;

junk f[];

int bj(int t)

{

    ans=min(ans,t);

    ts=;

}

int bj2(int l)

{

    lifenow=max(l,lifenow);

}

long long u;

long long p=0x2FFFFFF-;

void dfs1(int i,int dep,int l,int t)

{

    u++;

    if(u>p/) return ;

    bj2(l);

    if(t>ans) return ;

    if(l<f[i].t) return ;

    if(dep>=d)

    {

    bj(t);

    return ;

    }

    if(i>n) return ;

     if(d1[i][l]>||d2[t][l]>) return ;

    d1[i][l]++;

    d2[t][l]++;

    dfs1(i+,dep,l+f[i].l,f[i].t);

     dfs1(i+,dep+f[i].h,l,f[i].t);

     if(u>p/) return ;

}

}

int main()

{

    cin>>d>>n;

    int h=;

    int i,j,k;

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

    cin>>f[i].t>>f[i].l>>f[i].h;

    sort(f+,f+n+,cmp);

    dfs1(,,,);

    if(ts)

    cout<<ans;

    else cout<<lifenow;

    return ;

}

巴特西

洛谷 P1156 垃圾陷阱谈论剪枝，非满分

这是一个91分的非dp代码（是我太弱）

剪枝八五个（实际上根本没那么多，主要是上课装逼，没想到他们dp水过去了），不过我的思路与dp不同；

最新文章

热门文章

巴特西

洛谷 P1156 垃圾陷阱 谈论剪枝，非满分

这是一个91分的非dp代码（是我太弱）

剪枝八五个（实际上根本没那么多，主要是上课装逼，没想到他们dp水过去了），不过我的思路与dp不同；

最新文章

热门文章

洛谷 P1156 垃圾陷阱谈论剪枝，非满分