当前位置:首页 >> 学科竞赛 >>

GDOI2014 拯救莫莉斯


GDOI2014 拯救莫莉斯
莫莉斯· 乔是圣域里一个叱咤风云的人物,他凭借着自身超强的经济头脑,牢牢控制了圣域 的石油市场。 圣 域 的 地 图 可 以 看 成 是 一 个 n*m 的 矩 阵 。 每 个 整 数 坐 标 点 (x , y) 表 示 一 座 城 市 (1<=x<= n, 1<=y<=m) 。两座城市间相邻的定义为:对于城市(Ax

, Ay)和城市(Bx, By),满 足(Ax - Bx)^2 + (Ay - By)^2 = 1。 由于圣域的石油贸易总量很大,莫莉斯意识到不能让每笔石油订购单都从同一个油库里发 货。为了提高效率,莫莉斯· 乔决定在其中一些城市里建造油库,最终使得每一个城市 X 都 满足下列条件之一: 1.该城市 X 内建有油库, 2.某城市 Y 内建有油库,且城市 X 与城市 Y 相邻。 与地球类似, 圣域里不同城市间的地价可能也会有所不同, 所以莫莉斯想让完成目标的总花 费尽可能少。如果存在多组方案,为了方便管理,莫莉斯会选择建造较少的油库个数。

Input
第一行两个正整数 n,m ( n * m <= 50 且 m<=n),表示矩阵的大小。

接下来一个 n 行 m 列的矩阵 F,Fi, j 表示在城市(i,j)建造油库的代价。

Output
输出两个数,建造方案的油库个数和方案的总代价。

Sample Input
33

654

123

789

Sample Output
36

Data Constraint
对于30%数据满足 n * m <= 25;

对于100%数据满足 n * m <= 50; 0 <= Fi, j <= 100000 解题报告 根据本题的数据范围(n*m <= 50) ,可得列数 <= 7 因此,对于某一行,只有 2^7 个不同的状态 按照题目的定义,第 i 行的状态,只会对 i-1 行至 i+1 行产生影响 假设:F[i][j][k] 为对于前 i 行,第 i-1 行状态为 j, 第 i 行的状态为 k,并且对于任意一行 x (x<i) ,该行的所有城市满足题目的要求(附近城市里有油库) 。 F[i][j][k]的值表示其所能达到的最小代价 (辅助数组 G[i][j][k] 表示 F[i][j][k]所对应方案里的油库数量) F[i+1][k][X] = min(F[i][j][k] + cost[i+1][X]); (0 <= X <= 2m ) cost[i][j] 表示第 i 行,所取状态为 j 时所需要花费的代价。 转移方程中,X 状态可取,需使第 i 行的所有城市满足要求,即: (X or j or k or (k * 2) or (k / 2) ) and (2m - 1) = 2m - 1 答案:max(F[n+1][x][0]) 时间复杂度:23*m * n 空间复杂度:n * 22*m 期望得分:100 分 (0 <= X <= 2m )

Code:

Const Maxs=1 << 8; Maxn=55; con=1061109567; Var f,g: array[0..maxn,0..maxs,0..maxs]of Longint; n,m,max: Longint; cost: array[0..maxn,0..maxs,0..2]of Longint; Procedure Init(); Var i,j,k,x: Longint; Begin Readln(n,m); max:=(1 << m)-1; For i:=1 To n DO Begin For j:=1 To m Do BEgin Read(x); For k:=0 To max Do if k And (1 << (j-1))>=(1 << (j-1)) Then BEgin Inc(cost[i][k][1],x); Inc(cost[i][k][2]); End; End; End; Fillchar(f,sizeof(f),63); Fillchar(g,sizeof(g),63); For k:=0 To max Do Begin f[1][k][0]:=cost[1][k][1]; g[1][k][0]:=cost[1][k][2]; End; End; Procedure Main(); Var i,j,k,n_l,a1,a2: Longint; Begin For i:=1 To n Do For j:=0 To max Do For k:=0 To max Do Begin if f[i][j][k]=con Then Continue; For n_l :=0 To max Do if (n_l or j or k or (j<<1) or (j>>1))and max=max Then if f[i][j][k]+cost[i+1][n_l][1]<f[i+1][n_l][j] Then BEgin

f[i+1][n_l][j]:=f[i][j][k]+cost[i+1][n_l][1]; g[i+1][n_l][j]:=g[i][j][k]+cost[i+1][n_l][2]; End; End; a2:=MaxLongint; For k:=0 To max Do if (f[n+1][0][k]<a2)or((f[n+1][0][k]=a2)and(g[n+1][0][k]<a1)) Then Begin a1:=g[n+1][0][k]; a2:=f[n+1][0][k]; End; Writeln(a1,' ',a2); End; Begin Init(); Main(); End. Jason Victor Yan


相关文章:
GDOI2014 拯救莫莉斯
GDOI2014 拯救莫莉斯_学科竞赛_高中教育_教育专区。GDOI2014 拯救莫莉斯GDOI2014 拯救莫莉斯莫莉斯· 乔是圣域里一个叱咤风云的人物,他凭借着自身超强的经济头脑,牢...
更多相关标签:
gdoi2016 | gdoi协议 | gdoi省队 | gdoi 珠海一中 | gdoi什么时间考 | gdoi 2016 day2 题目 | gdoi是什么 | gdoi2016广东赛区成绩 |