P1910 L国的战斗之间谍

链接：P1910

----------------------------------------------

一看题目，这是道二维背包

然而暴力出奇迹啊

我就写了个dfs

然后TLE，吸了氧也TlE，

怎么办呢，剪枝！！1

---------------------------------------------

思路：搜索，（我写的奇奇怪怪，题解都是搜索请不请第i个人，我写的是当还剩下

多少能力和钱（雾））

这种写法实在太奇怪了，以至于还要剪枝，还有一个奇葩边界条件qwq。

就是大体是搜索每一种可行组合，然后如果在这一轮没有扩展任何状态，就更新一下答案

竟然能过（剪枝后不开02）。

剪枝：我们枚举的是组合，就递归的时候记下来上一个人是谁，然后从他开始枚举，就可以

优化ac了

（数据太小了）

要不是记忆化wa了一半我才不写暴力呢

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,x;
int a[10001];
int b[10001];
int c[10001];
int ans;
int vis[100001];
int ff[1001][1001];
int dfs(int able,int mo){
    int f=0;
    if(ff[able][mo])
    return ff[able][mo];
    for(int i=1;i<=n;++i){
        if(!vis[i])
            if(b[i]<=able&&c[i]<=mo){
                f=1;
                vis[i]=1;
                ff[able][mo]=max(ff[able][mo],dfs(able-b[i],mo-c[i])+a[i]);
                vis[i]=0;
            }    
    }
    if(f==0){
        return 0;
    }
    else{
    return ff[able][mo];
    }
}

int main(){
    cin>>n>>m>>x;
    for(int i=1;i<=n;++i)
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
    dfs(m,x);
        cout<<ff[m][x];
    return 0;
}

记忆化50分

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,x;
int a[10001];
int b[10001];
int c[10001];
int ans;
int vis[100001];
void dfs(int able,int mo,int z,int num){
    int f=0;
    for(int i=num;i<=n;++i){
        if(!vis[i])
            if(b[i]<=able&&c[i]<=mo){
                f=1;
                vis[i]=1;
                dfs(able-b[i],mo-c[i],z+a[i],i+1);
                vis[i]=0;
            }    
    }
    if(f==0){
        ans=max(ans,z);
        return ;
    }
}

int main(){
    cin>>n>>m>>x;
    for(int i=1;i<=n;++i)
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
    dfs(m,x,0,1);
        cout<<ans;
    return 0;
}

发送评论 编辑评论

发送评论编辑评论