CodeVs 2651

题目链接：孔子教学

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int a[1000],b[1000];
bool vis[1000];
int x,y,z,maxx = -1e9;
void dfs(int k,int ren,int ans,int time)
{
    if(ren >= z && time >= 0) maxx=max(maxx,ans);
    if(ren == x || k==x) return ;
    for(int i=k+1;i<=x;i++)
    {
        if(time>=b[i]&&!vis[i]) 
        {
            vis[i]=true;
            dfs(i,ren+1,ans+a[i],time-b[i]);
            vis[i]=false;
        } 
    }
}
int main()
{
	char ch;
	scanf("%d%d%d",&x,&z,&y);
	for(int i=1;i<=x;i++)
	{
		cin>>ch;
		if(ch == 'G')
			a[i] = 3;
		if(ch == 'M')
			a[i] = 2;
		if(ch == 'B')
			a[i] = -2;
		scanf("%d",&b[i]);
	}
	dfs(0,0,0,y);
	if(maxx == -1e9)
	cout<<-1<<endl;
	else 
	cout<<maxx<<endl;
	return 0;
} 

低配版。。。

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
int a[1000],b[1000];
bool vis[1000];
int x,y,z,maxx = -1e9;
void dfs(int k,int ren,int time,int ans)
{
	for(int i=k+1;i<=x;i++)
	{
		if(!vis[i])
		{
			vis[i] = 1;
			ren ++;
			time -= b[i];
			ans += a[i];
			if(ren == z && time >= 0)
			{
				if(ans > maxx)
					maxx = ans;
			}
			else dfs(i,ren,time,ans);
			vis[i] = 0;
			ren --;
			time += b[i];
			ans -= a[i];
		}
	}
}
int main()
{
	char ch;
	scanf("%d%d%d",&x,&z,&y);
	for(int i=1;i<=x;i++)
	{
		cin>>ch;
		if(ch == 'G')
			a[i] = 3;
		if(ch == 'M')
			a[i] = 2;
		if(ch == 'B')
			a[i] = -2;
		scanf("%d",&b[i]);
	}
	dfs(0,0,y,0);
	if(maxx == -1e9)
	cout<<-1<<endl;
	else 
	cout<<maxx<<endl;
	return 0;
}