tyvj 1061 Mobile Service
2024-08-29 23:46:08
线性DP
本题的阶段很明显,就是完成了几个请求,但是信息不足以转移,我们还需要存储三个服务员的位置,但是三个人都存的话会T,我们发现在阶段 i 处,一定有一个服务员在 p[i] 处,所以我们可以只存另外两个人的位置,而且本题要滚动数组,采用刷表法比较好
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int init() {
int rv = 0, fh = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') fh = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
rv = (rv<<1) + (rv<<3) + c - '0';
c = getchar();
}
return rv * fh;
}
int c[205][205], n, dp[2][205][205], p[2005], ans = 0x3f3f3f3f, q;
int main() {
n = init(); q = init();
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
c[i][j] = init();
}
}
for(int i = 1; i <= q; i++) p[i] = init();
memset(dp, 0x3f, sizeof(dp));
p[0] = 1;
dp[0][2][3] = 0;
dp[0][3][2] = 0;
for(int i = 0; i < q; i++) {
for(int j = 1; j <= n; j++)
for(int k = 1; k <= n; k++)
dp[!(i & 1)][j][k] = 0x3f3f3f3f;
for(int j = 1; j <= n; j++) {
for(int k = 1; k <= n; k++) {
dp[!(i & 1)][j][k] = min(dp[!(i & 1)][j][k], dp[i & 1][j][k] + c[p[i]][p[i + 1]]);
dp[!(i & 1)][p[i]][k] = min(dp[!(i & 1)][p[i]][k], dp[i & 1][j][k] + c[j][p[i + 1]]);
dp[!(i & 1)][j][p[i]] = min(dp[!(i & 1)][j][p[i]], dp[i & 1][j][k] + c[k][p[i + 1]]);
}
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
ans = min(ans, dp[(q & 1)][i][j]);
}
}
cout << ans << endl;
return 0;
}
最新文章
- jdbc 设置连接支持多条sql
- js获取url地址中的参数
- linux下文件系统类型的学习
- HackerRank ";Morgan and a String";
- Android实现静默安装与卸载
- C#控制定位Word光标移动到任意行或者最后一行,取得光标位置等操作
- OpenCV——CvMatchShapes函数
- linux内核源码阅读之facebook硬盘加速flashcache之八
- jQuery 层级选择器 + keyCode
- 定制自己的Unity脚本模板
- js 高级算法 - 动态规划
- java中一个引人深思的匿名内部类
- SAP S4系统创建Customer和Vendor的BAPI
- Eigen实现坐标转换
- navicat for mysql 注册码,简简单单,一个搞定(蔡军帅亲测有效)
- 金蝶PDA金蝶盘点机金蝶仓库条码管理方案-采购入库单教程
- Hive配置永久显示表字段名并且不显示表名
- 未能加载文件或程序集“Oracle.DataAccess”或它的某一个 依赖项。如何解决?
- filter 死循环(tomcat 启动完成 ,自动执行filter.dofilter,导致tomcat 启动超时) , tomcat 启动和 servers 启动 不同
- comgrid获取多选值