codeforces 793 D. Presents in Bankopolis（记忆化搜索）
2024-09-01 06:05:17
题目链接：http://codeforces.com/contest/793/problem/D
题意：给出n个点m条边选择k个点，要求k个点是联通的而且不成环，而且选的边不能包含选过的边不能包含以前
选过的点，问最小的权值是多少。
题解：像这种取最小的一般可以考虑一下dp，然后再看一下题目，由于每次选的边都不能包括以前选的点，所以每
选择一条边能选择的区间范围就缩小了。
设dp[pos][l][r][k](这里可能会有人觉得开80*80*80*80会不会有点大了，自行计算一下不会爆内存的)，pos表示当前位置，l表示区间左端点，r表示区间右端点，k表示还剩下多少条边没选当然也可以
设选了多少条边。附上记忆化搜索代码
int dfs(int pos , int l , int r , int count) {
if(dp[pos][l][r][count] != -1) {
return dp[pos][l][r][count];
}
if(count == 1) {
dp[pos][l][r][count] = 0;
return 0;
}
int sum = inf;
for(int i = 1 ; i <= n ; i++) {
if(mmp[pos][i] != inf) {
if(i > l && i < r) {
int sta = l , end = r;
if(i < pos) {
end = pos;
}
else {
sta = pos;
}
sum = min(sum , dfs(i , sta , end , count - 1) + mmp[pos][i]);
}
}
}
dp[pos][l][r][count] = sum;
return sum;
}
#include <iostream>
#include <cstring>
#include <cstdio>
#define inf 0X3f3f3f3f
using namespace std;
const int M = 82;
int n , k , m , u , v , c;
int mmp[M][M] , dp[M][M][M][M];
int dfs(int pos , int l , int r , int count) {
if(dp[pos][l][r][count] != -1) {
return dp[pos][l][r][count];
}
if(count == 1) {
dp[pos][l][r][count] = 0;
return 0;
}
int sum = inf;
for(int i = 1 ; i <= n ; i++) {
if(mmp[pos][i] != inf) {
if(i > l && i < r) {
int sta = l , end = r;
if(i < pos) {
end = pos;
}
else {
sta = pos;
}
sum = min(sum , dfs(i , sta , end , count - 1) + mmp[pos][i]);
}
}
}
dp[pos][l][r][count] = sum;
return sum;
}
int main() {
scanf("%d%d" , &n , &k);
scanf("%d" , &m);
memset(mmp , inf , sizeof(mmp));
for(int i = 0 ; i < m ; i++) {
scanf("%d%d%d" , &u , &v , &c);
mmp[u][v] = min(mmp[u][v] , c);
}
memset(dp , -1 , sizeof(dp));
int ans = inf;
for(int i = 1 ; i <= n ; i++) {
ans = min(ans , dfs(i , 0 , n + 1 , k));
}
if(ans == inf) {
printf("-1\n");
}
else {
printf("%d\n" , ans);
}
return 0;
}
最新文章
- Mysql日期时间大全
- p标签中的span标签文字垂直居中对齐
- wikioi 1430 素数判定
- android tween动画效果
- Light OJ 1037 - Agent 47（预处理状态压缩DP）
- angularJS常用命令
- 致网友Wonderfei的一封信（怎样选择自己主动化框架的几点拙见)
- 第三届蓝桥杯Java高职组决赛第一题
- Flask 学习 十四 测试
- OpenCV 闭合轮廓检测
- Mybatis常见问题总结
- jquery首页图片轮播
- linux-安装-源码安装
- java空心菱形
- ROS中发布IMU传感器消息
- Feign来调用服务
- hdu 1760 DFS+博弈
- maven 笔记：maven Could not create the Java Virtual Machine
- Android "Please ensure that adb is correctly located at" 错误
- su对环境变量做了什么