首页 > 代码库 > UVA 1379 - Pitcher Rotation(DP + 贪心)
UVA 1379 - Pitcher Rotation(DP + 贪心)
题目链接:1379 - Pitcher Rotation
题意:n个人,m个敌人,去比赛,有得分,n个人可以重复比,但是每次比完要休息4天,问最大得分
思路:dp[i][j][k][l][x] 表示第场比赛,前一天为j,两天为k,三天为l,四天为x,的最大得分,然后由于只有每个人5天就能用一次,所以对于每个人来说,只有得分前5的会被使用上,所以后4维状态只需要5^4,进行状态转移,不用比赛的情况分开考虑,还有这题内存有限,要用滚动数组优化不然会RE
代码:
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; #define max(a,b) ((a)>(b)?(a):(b)) const int N = 105; const int M = 205; int t, n, m, G, d[M + 10], i, x, j, k, l, y, dp[2][6][6][6][6], ans; struct Map { int v, id; } g[N][N]; bool cmp(Map a, Map b) { return a.v > b.v; } int cal(int u, int v) { if (u == 0 || v == 0) return 0; return g[u][v].id; } int main() { scanf("%d", &t); while (t--) { ans = 0; scanf("%d%d%d", &n, &m, &G); for (i = 1; i <= m; i++) { for (j = 1; j <= n; j++) { scanf("%d", &g[i][j].v); g[i][j].id = j; } sort(g[i] + 1, g[i] + 1 + n, cmp); } G += 10; for (i = 1; i <= G; i++) scanf("%d", &d[i]); memset(dp[0], 0, sizeof(dp[0])); for (i = 1; i <= G; i++) { int now = i % 2; int pre = (!now); memset(dp[now], 0, sizeof(dp[now])); if (d[i]) { for (y = 1; y <= 5; y++) { for (j = 0; j <= 5; j++) { if (i > 1 && cal(d[i], y) == cal(d[i - 1], j)) continue; for (k = 0; k <= 5; k++) { if (i > 2 && cal(d[i], y) == cal(d[i - 2], k)) continue; for (l = 0; l <= 5; l++) { if (i > 3 && cal(d[i], y) == cal(d[i - 3], l)) continue; for (x = 0; x <= 5; x++) { if (i > 4 && cal(d[i], y) == cal(d[i - 4], x)) continue; dp[now][y][j][k][l] = max(dp[now][y][j][k][l], dp[pre][j][k][l][x] + g[d[i]][y].v); ans = max(ans, dp[now][y][j][k][l]); } } } } } } else { for (j = 0; j <= 5; j++) { for (k = 0; k <= 5; k++) { for (l = 0; l <= 5; l++) { for (x = 0; x <= 5; x++) { dp[now][0][j][k][l] = max(dp[now][0][j][k][l], dp[pre][j][k][l][x]); ans = max(ans, dp[now][0][j][k][l]); } } } } } } printf("%.2lf\n", ans * 1.0 / 100); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。