建议用dfs写,dfs虽然慢但很准确,也很好写
by LYM20114 @ 2022-01-20 16:59:53
100分dfs:
```cpp
#include <iostream>
using namespace std;
int n,m,sum,sumv,maxn = -1;
int val[25][25],res1[25],res2[25];
void dfs(int start){
if(start == n + 1){
sum = 0;
for(int i = 1;i <= n;i++){
if(res1[i] != 0) sum += val[i][res1[i]];
}
if(sum > maxn){
maxn = sum;
for(int i = 1;i <= n;i++){
res2[i] = res1[i];
}
}
return;
}
for(int i = 0;i <= m;i++){
if((sumv + i) <= m){
sumv += i;
res1[start] = i;
dfs(start + 1);
res1[start] = 0;
sumv -= i;
}
else return;
}
}
int main(){
cin >> n >> m;
for(int i = 1;i <= n;i++){
for(int j = 1;j <= m;j++){
cin >> val[i][j];
}
}
dfs(1);
cout << maxn << endl;
for(int i = 1;i <= n;i++){
cout << i << " " << res2[i] << endl;
}
return 0;
}
by LYM20114 @ 2022-01-20 17:00:29
搜的思路比较奇怪,仅供参考
by LYM20114 @ 2022-01-20 17:02:02
还有,不建议用万能头文件,很慢且不能用map
by LYM20114 @ 2022-01-20 17:03:49
@[LYM2011](/user/531776) 为什么万能库不能用map
by caocao666 @ 2022-01-22 21:19:02
试过,不能用map,不然会报错,不过有可能版本不同
by LYM20114 @ 2022-02-01 20:09:22
@[caocao666](/user/350696)
by LYM20114 @ 2022-02-01 20:09:54
@[LYM2011](/user/531776)
谢谢 可能是版本不同
by caocao666 @ 2022-02-11 10:13:39