编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

终于AC了

注意从大到小排序。

编译通过...

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

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

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

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

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

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

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

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

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

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

终于全0了

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

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

用了EOF才过的 用SEEKEOF老是错

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

呵呵

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

主要的思路无非是搜索

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

第四个数据是什么？

没过

过了。

乱七八糟一大堆剪枝

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

搜索

随便加两个上下界就行了

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

/*
可以可以
这题很神..
害怕啊
我们很容易看到这很明显是搜索
咋搜~！复杂度太高根本不行啊
那么我们先加个剪枝！
记录下总书写质量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;
}   

#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分，谁能优化？

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