首页 > 代码库 > uva 1379 - Pitcher Rotation(dp)
uva 1379 - Pitcher Rotation(dp)
题目链接:uva 1379 - Pitcher Rotation
题目大意:给出n,表示由n个人组成的战队,接着是m,表示有m个敌人,g表示要比赛的天数,给出g后,比赛的天数起始是g+10,然后是一个m*n的矩阵,g[i][j]表示第j个敌人被i打败后,战队所得到的分数。然后g+10个数,表示每天需要挑战的敌人是谁,0代表说休息;每个人出战的次数没有限制,但是比过一场后要休息4天,问说战队的最高得分。
解题思路:注意题目中的一点,说每个人比完一场赛后要休息4天,那么也就是说对于每个敌人来说,被派去和他打的人就只可能是得分比较高的5个。所以只用开dp[i][a][b][c][d]表示第i天时,第i-1天为a,i-2为b,i-3为c,i-4为d(这里的a,b,c,d表示说那天所对应敌人的前5个较大得分的序号)然后转移到dp[i+1][x][a][b][c],x所对应的序号要和a,b,c,d对应的人的序号不同。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 105; const int M = 10; struct state { int val, u; }g[N][N]; int n, m, d, t[N*3]; int dp[2][M][M][M][M]; inline bool cmp (const state& a, const state& b) { return a.val > b.val; } inline int cat (int j, int i) { if (j == 0 || i == 0) return 0; return g[i][j].u; } void init () { scanf("%d%d%d", &n, &m, &d); for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { scanf("%d", &g[i][j].val); g[i][j].u = j; } sort(g[i]+1, g[i] + n + 1, cmp); } d += 10; for (int i = 1; i <= d; i++) scanf("%d", &t[i]); } double solve () { memset(dp[0], 0, sizeof(dp[0])); for (int i = 1; i <= d; i++) { int now = i%2; int pre = 1-now; memset(dp[now], 0, sizeof(dp[now])); if (t[i]) { for (int j = 1; j <= 5; j++) { for (int x = 0; x <= 5; x++) { if (i > 1 && cat(j, t[i]) == cat(x, t[i-1])) continue; for (int y = 0; y <= 5; y++) { if (i > 2 && cat(j, t[i]) == cat(y, t[i-2])) continue; for (int z = 0; z <= 5; z++) { if (i > 3 && cat(j, t[i]) == cat(z, t[i-3])) continue; for (int a = 0; a <= 5; a++) { if (i > 4 && cat(j, t[i]) == cat(a, t[i-4])) continue; dp[now][j][x][y][z] = max(dp[now][j][x][y][z], dp[pre][x][y][z][a] + g[t[i]][j].val); } } } } } } else { for (int x = 0; x <= 5; x++) { for (int y = 0; y <= 5; y++) { for (int z = 0; z <= 5; z++) { for (int a = 0; a <= 5; a++) { dp[now][0][x][y][z] = max(dp[now][0][x][y][z], dp[pre][x][y][z][a]); } } } } } } int ans = 0; int u = d%1; for (int x = 0; x <= 5; x++) for (int y = 0; y <= 5; y++) for (int z = 0; z <= 5; z++) for (int a = 0; a <= 5; a++) ans = max(ans, dp[u][x][y][z][a]); return ans / 100.0; } int main () { int cas; scanf("%d", &cas); while (cas--) { init (); printf("%.2lf\n", solve()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。