栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

zoj 3135 Roommate

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

zoj 3135 Roommate

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <cstdlib>#include <algorithm>#include <vector>using namespace std;const int maxn = 305;const int K = 101;int T1[maxn], T2[maxn], a[maxn], b[maxn];int dp[maxn][maxn][205];void update(int& x, int v){ if(x == -1 || x > v) x = v;}int main() { int test, n, n1, n2; scanf("%d", &test); while(test --){ scanf("%d", &n); for(int i = 0; i < n; i ++) scanf("%d", &T1[i]); for(int i = 0; i < n; i ++) scanf("%d", &T2[i]); scanf("%d%d", &n1, &n2); for(int i = 0; i < n1; i ++){ scanf("%d", &a[i]); a[i] --; } for(int i = 0; i < n2; i ++){ scanf("%d", &b[i]); b[i] --; } for(int i = 0; i <= n1; i ++){ for(int j = 0; j <= n2; j ++){ for(int l = 0; l <= 2*K; l ++){ dp[i][j][l] = -1; } } } dp[0][0][K] = 0; int ans = -1; for(int i = 0; i <= n1; i ++){ for(int j = 0; j <= n2; j ++){ for(int l = 0; l <= 2*K; l ++){ if(dp[i][j][l] == -1) continue; if(i == n1 && j == n2){ int x = dp[i][j][l] + max(0, l-K); update(ans, x); } if(i != n1){ int v = l - K, tmp = dp[i][j][l]; if(v < 0 && b[j-1] == a[i]) v = 0; if(v > 0){ tmp += v; v = 0; } update(dp[i+1][j][T1[a[i]]+v + K], tmp); } if(j != n2){ int v = l - K, tmp = dp[i][j][l]; if(v > 0 && a[i-1] == b[j]){ tmp += v; v = 0; } if(v < 0) v = 0; update(dp[i][j+1][-T2[b[j]]+v + K], tmp + T2[b[j]]); } } } } printf("%dn", ans); } return 0;}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/378609.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号