92 条题解

  • 0
    @ 2006-11-01 09:22:34

    编译通过...

    ├ 测试数据 01:答案正确... 822ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 462ms

    ├ 测试数据 10:答案正确... 259ms

    从大到小排序之后怎么还是这样呢?加了一大堆剪枝..朴素的枚举只能过三组.

  • 0
    @ 2006-10-26 19:06:31

    宝剑锋从磨练出,梅花香自苦寒来!!

    终于AC了

    注意从大到小排序。

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    终于全0了

    楼下的同学也没免太.........

  • 0
    @ 2006-09-18 20:39:04

    终于AC了-_-||至少交了10次

    用了EOF才过的 用SEEKEOF老是错

    开始只用最优减枝也超时 不知道楼下的怎么过的

    编译通过...

    ├ 测试数据 01:答案正确... 41ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 270MS

  • 0
    @ 2006-08-31 12:54:44

    DFS搜索,用inline 优化,加最优化剪枝,最后Cheating掉两个点:(1 & 10)

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 100ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:100ms

  • 0
    @ 2006-07-21 16:50:50

    编译通过...

    ├ 测试数据 1:答案正确... 212ms

    ├ 测试数据 2:答案正确... 0ms

    ├ 测试数据 3:答案正确... 0ms

    ├ 测试数据 4:答案正确... 0ms

    ├ 测试数据 5:答案正确... 0ms

    ├ 测试数据 6:答案正确... 0ms

    ├ 测试数据 7:答案正确... 0ms

    ├ 测试数据 8:答案正确... 0ms

    ├ 测试数据 9:答案正确... 0ms

    ├ 测试数据 10:答案正确... 712ms

    呵呵

    写个题解,庆祝一下,主要是给自己看~~呵呵~~

    主要的思路无非是搜索

    我没用那么强的剪枝{主要是不会>_

  • 0
    @ 2006-06-11 08:02:47

    第四个数据是什么?

    没过

  • 0
    @ 2006-02-07 10:49:53

    过了。

    乱七八糟一大堆剪枝

    最后每个数据都是0ms^_^

  • 0
    @ 2006-01-27 23:51:16

    搜索

    随便加两个上下界就行了

  • 0
    @ 2006-01-22 16:19:00

    搜索题,加一点剪枝就可以过。

  • -1
    @ 2017-05-07 22:20:57
    /*
    可以可以
    这题很神..
    害怕啊
    我们很容易看到这很明显是搜索
    咋搜~!复杂度太高根本不行啊
    那么我们先加个剪枝!
    记录下总书写质量s[]
    那么如果当前选择到了cur
    有s[n]-s[cur]<当前ans
    果断剪枝
    那么这样就可以过八个点了
    进一步优化
    我们可以先将小精灵按照书写质量从大到小排序
    这样可以更有可能一开始就找到一个更大的ans
    就方便进行剪枝了
    但是这样还是不好过的
    题解和博客有很多进一步强势剪枝
    窝比较弱直接卡时了~
    0.25就能A..
    */
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <ctime>
    using namespace std;
    
    const int MAXN=52;
    struct node
    {
        int w,idx;
        bool operator <(const node& b)const
        {
            return w>b.w;
        }
    }a[MAXN];
    int s[MAXN];
    bool nocan[MAXN][MAXN];
    int g[MAXN];
    int ans;
    int n,l;
    
    void init()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i].w);
            s[i]=s[i-1]+a[i].w;
            a[i].idx=i;
        }
        int x,y;
        while(scanf("%d%d",&x,&y)==2)
            nocan[x][y]=nocan[y][x]=1;
    }
    
    void dfs(int cur,int havew)
    {
        if(((double)clock()/CLOCKS_PER_SEC)>0.25)
        {
            cout<<ans<<endl;
            exit(0);
        }
        if(cur>n)
        {
            ans=max(ans,havew);
            return;
        }
        if(havew+s[n]-s[cur-1]<ans)
            return;
        bool flag=1;
        for(int i=1;i<=l;i++)
        {
            if(nocan[g[i]][a[cur].idx])
                flag=0;
        }
        if(flag)
        {
            g[++l]=a[cur].idx;
            dfs(cur+1,havew+a[cur].w);
            l--;
        }
        dfs(cur+1,havew);
    }
    
    int main()
    {
        init();
        sort(a+1,a+n+1);
        dfs(1,0);
        cout<<ans<<endl;
        return 0;
    }   
    
  • -1
    @ 2015-10-04 17:26:31

    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<queue>
    #include<vector>
    using namespace std;
    int n;
    int d[52][52];
    int vis[53];
    int yu[52];
    int q[53];
    int sum=0;

    int mo(int *vis)
    {

    for(int i=1;i<=n;i++)
    {
    for(int k=1;k<i;k++)
    {
    if(vis[i]&&vis[k]&&d[i][k])return 0;
    }
    }
    return 1;
    }
    void ans(int x,int flog,int wath)
    { if(flog)vis[x]=1;
    else{vis[x]=0;}

    if(x==n){if(mo(vis))sum=max(sum,wath);return ;}

    if(sum==0||(sum&&wath+q[x+1]>sum))ans(x+1,1,wath+yu[x+1]);
    if(sum==0||(sum&&wath+q[x+2]>sum))ans(x+1,0,wath);
    }
    int main()
    {
    memset(q,0,sizeof(q));
    memset(d,0,sizeof(d));
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    cin>>yu[i];
    }
    int x,y;
    while(scanf("%d%d",&x,&y)!=EOF){
    d[y][x]=1;
    d[x][y]=1;
    }

    for(int i=n;i>=1;i--)
    {
    q[i]=yu[i]+q[i+1];
    }ans(1,1,yu[1]);

    memset(vis,0,sizeof(vis));
    ans(1,0,0);

    cout<<sum;

    return 0;
    }
    40分,谁能优化?

  • -2
    @ 2017-03-24 11:06:24

    Accepted

    状态 耗时 内存占用

    #1 Accepted 11ms 328.0KiB
    #2 Accepted 1ms 336.0KiB
    #3 Accepted 1ms 328.0KiB
    #4 Accepted 1ms 332.0KiB
    #5 Accepted 1ms 332.0KiB
    #6 Accepted 1ms 464.0KiB
    #7 Accepted 1ms 332.0KiB
    #8 Accepted 2ms 456.0KiB
    #9 Accepted 7ms 336.0KiB
    #10 Accepted 4ms 328.0KiB

信息

ID
1048
难度
7
分类
搜索 | 搜索与剪枝 点击显示
标签
递交数
2369
已通过
419
通过率
18%
被复制
14
上传者