90pts求调(必关)
查看原帖
90pts求调(必关)
1593174
wanjunyu2013楼主2025/8/5 16:28
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define L_N LLONG_MIN
#define L_M LLONG_MAX
const int N=2e2+10;
int noip;
int v,g;
int vs[30],co[N][N];
int minn=L_M;
int da[30][30];
int ns[100];
int fa=1;
int za;
bool pd() {
	for(int i=1; i<=v; i++) {
		if(ns[i]<vs[i])
			return false;
	}
	return true;
}
void dfs(int dp,int nw,int ct) {
	for(int i=1; i<=v; i++) {
		ns[i]+=co[nw][i];
	}
	da[fa][ct]=nw;
	if(pd()&&ct<minn) {
		minn=ct;
		za=fa;
		fa++;
		return;
	}
	for(int i=nw+1; i<=g; i++) {
		dfs(dp+1,i,ct+1);
		for(int j=1; j<=v; j++) {
			ns[j]-=co[i][j];
		}
	}
}

void ap() {
	cin>>v;
	for(int i=1; i<=v; i++)
		cin>>vs[i];
	cin>>g;
	for(int i=1; i<=g; i++)
		for(int j=1; j<=v; j++)
			cin>>co[i][j];
	dfs(1,0,0);
	cout<<minn<<" ";
	for(int i=1; i<=minn; i++)
		cout<<da[za][i]<<" ";
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	noip=1;
	//cin>>noip;
	while(noip--) {
		ap();
	}
	return 0;
}	
2025/8/5 16:28
加载中...