求助 30pts 部分分 dfs
查看原帖
求助 30pts 部分分 dfs
238711
Dream_Loner楼主2023/8/14 18:41

样例过了 哪里有问题啊

#include<bits/stdc++.h>
#define ll long long
#define tim first
#define val second
using namespace std;
const int N=101;
int t,m,ans,sum,cnt;
array<pair<int,int>,N> a;
array<bool,N> vis;
void dfs(int pos)
{
    if(pos==m+1)
    {
        for(int i=1;i<=m;i++)
        {
            if(vis[i]==1) sum+=a[i].val;
        }
        if(cnt<=t) ans=max(ans,sum);
        return;
    }
    else
    {
        for(int i=0;i<=1;i++)
        {
            vis[pos]=i;
            cnt+=i*a[pos].tim;
            dfs(pos+1);
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>t>>m;
    for(int i=1;i<=m;i++) cin>>a[i].tim>>a[i].val;
    dfs(1);
    cout<<ans;
    return 0;
}

2023/8/14 18:41
加载中...