AcWing 1013. 机器分配(超级dfs)
原题链接
简单
作者:
Air1222
,
2024-03-18 20:41:27
,
所有人可见
,
阅读 7
#include <iostream>
using namespace std;
const int N=15,M=20;
int w[N][M];
int n,m;
int res;
int st[N];
void dfs(int wage,int sum,int start)
{
if(sum<0)return;
if(res<wage)
{
res=wage;
}
for(int i=start;i<=n;i++)
for(int j=0;j<=sum;j++)
if(sum>0)
dfs(wage+w[i][j],sum-j,i+1);
}
bool dfs_2(int wage,int begin,int sum)
{
if(wage==res)
{
for(int i=1;i<=n;i++)
cout<<i<<" "<<st[i]<<endl;
return true;
}
for(int i=begin;i<=n;i++)
for(int j=0;j<=sum;j++)
{
st[i]=j;
if(dfs_2(wage+w[i][j],i+1,sum-j))return true;
st[i]=0;
}
return false;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>w[i][j];
dfs(0,m,1);
cout<<res<<endl;
dfs_2(0,1,m);
return 0;
}