17111 Football team
2024-10-01 05:17:49
时间限制:1000MS 内存限制:65535K
提交次数:0 通过次数:0
题型: 编程题 语言: C++;C
Description
As every one known, a football team has 11 players . Now, there is a big problem in front of the Coach Liu. The final contest is getting closer.
Who is the center defense, the full back or the forward? ...... There are n wonderful players for n positions in the team and Coach Liu know
everyone's abilities at different positions in matches. Assume that the team's power is the sum of the abilities of all n players according to
their positions, could you help Coach Liu to find out the max power his team can get?
输入格式
The first line is an integer n(n<11). Followed by n rows. Each row has n integer (0 to 1000) which represents the abilities of one player
at different positions.
输出格式
The max power.
输入样例
10
4 6 3 3 4 5 7 4 9 0
5 9 3 4 6 1 7 3 9 3
1 5 8 0 5 4 2 7 9 3
4 6 9 4 7 3 7 9 5 4
2 0 1 3 2 5 8 4 6 2
1 5 8 4 2 6 8 0 4 2
1 4 2 6 8 9 4 2 6 8
1 2 9 5 6 4 2 7 5 7
2 4 7 5 8 5 3 2 6 4
2 4 6 4 8 7 3 5 7 3
输出样例
76 简单回溯:wa在由于now是全局变量,在每一次到达结束状态时,now的值不会因递归返回而改变(不像局部变量),而我是希望在递归枚举所有情况是now的值应该是返回上一状态的,
故因 加一句:now-=mat[i][j]
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
int mat[12][12];
int vis[12];
int now=0;
int maxr=0;
void dfs(int cur)
{
int i;
if(cur==n) {if(now>maxr) maxr=now;}
else for(i=0;i<10;++i){
if(!vis[i]){
now+=mat[cur][i];//尝试选择第cur行第i列的数
vis[i]=1;
dfs(cur+1);
vis[i]=0;
now-=mat[cur][i];//谨记,now需随递归返回原来的值
} }
}
int main()
{
memset(vis,0,sizeof(vis));
memset(mat,0,sizeof(mat));
scanf("%d",&n);
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
scanf("%d",&mat[i][j]);
dfs(0);
printf("%d\n",maxr);
}
最新文章
- ubuntu install eclipse-installer
- 针对bootstrap内联单选框input与文字不能居中对齐的解决办法
- javascript面试题(一)
- MFC重载关闭按钮
- android中scrollTo和scrollBy的理解
- 做好织梦dedecms安全防护全部方法
- UVA 1839 Alignment
- if __name__ == &#39;__main__&#39; 到底是何方神圣(转)
- BZOJ_4448_[Scoi2015]情报传递_主席树
- openstack搭建之-nova配置(10)
- Flask插件wtforms、Flask文件上传和Echarts柱状图
- 用Flask+Redis维护Cookies池
- 【Mysql】事务的四种特性和隔离级别
- Don&#39;t forget to Cherish
- linux常用命令:cp 命令
- Kali linux apt-get update 失败,无release……(最有效)
- 匿名函数lambda,过滤函数filter,映射类型map
- day29 python 套接字socket TCP udp 形式发送信息的区别
- [Microsoft][ODBC Microsoft Access Driver] 参数不足,期待是 1
- 唯一索引 &;&; 主键索引