洛谷p1559运动员最佳匹配问题
2024-09-07 22:51:24
搜索 可行性剪枝
虽然这题目是我搜二分图的标签搜到的
但是n比较小
明显可以暴力
然而只有80分
再加上可行性剪纸就行啦
就是记所有运动员他所能匹配到的最大值、
在我们搜索到第i层的时候
如果他后边的运动员的最大值加起来还比当前已经搜到的最优解还小的话
就把他减掉
Code:
//bao li
#include <cstdio>
#include <iostream>
using namespace std;
const int N = ;
int n, a[N][N], b[N][N], maxn[N], ans;
bool vis[N];
int read() {
int s = , w = ;
char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') w = -; ch = getchar();}
while(isdigit(ch)) {s = s * + ch - ''; ch = getchar();}
return s * w;
}
void dfs(int dep, int w) {
if(dep > n) {ans = max(ans, w); return;}
int sum = ;
for(int i = dep; i <= n; i++) sum += maxn[i];
if(w + sum < ans) return;
for(int i = ; i <= n; i++)
if(!vis[i]) {
vis[i] = ;
dfs(dep + , w + a[dep][i] * b[i][dep]);
vis[i] = ;
}
}
int main() {
n = read();
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
a[i][j] = read();
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
b[i][j] = read();
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)
maxn[i] = max(maxn[i], a[i][j] * b[j][i]);
dfs(, );
cout << ans << endl;
return ;
}
谢谢收看, 祝身体健康!
最新文章
- Adaboost\GBDT\GBRT\组合算法
- JS数组求最大值和最小值
- SQL 谜题(硬币的组合)
- OpenCASCADE Conic to BSpline Curves-Parabola
- windows平台整合Apache与tomcat
- SQL触发器实例讲解
- Vue 子组件向父组件传参
- 浅谈Java泛型之<;? extends T>;和<;? super T>;的区别
- this computer does not support Intel Virtualization Technology (VT-x) .Haxm can&#39;not be installed
- Android 屏幕刷新机制
- UE4成批处理透明材质
- Error:Failed to resolve: :Base:
- webapi快速开发框架
- Map不同具体实现类的比较和应用场景的分析
- 数论卷积公式and莫比乌斯反演
- Spring+Struts+Mybatis+Shiro整合配置
- css--纵向margin设置auto和百分数真的无效吗?
- 通过分析Ajax请求 抓取今日头条街拍图集
- JAVA对URL的解码【转】
- java-JProfiler(二)-进行本地JVM的性能监控-tomcat