「JoyOI1469」飘飘乎数独

2014年3月4日2,2840

背景 Background

为了能够赶在Candy生日这天送给她一个特制的礼物,飘飘乎居士最近一直躲在家中研究自己发明的飘飘乎数独

描述 Description

飘飘乎数独每行的数字都由1~m自然数填满(每行中每个数字用且只能用一次),但相邻的自然数(5 4与4 5都认为相邻)却不会出现在相邻的方格中(包括左右相邻和上下相邻),对于这样的一个飘飘乎数独,当然有许许多多的填法。但是,飘飘乎数独每一列都有一个得分规则:第i列的得分为第i列所有自然数的总和*i,最后的总分即为m列得分之和。飘飘乎居士当然希望给Candy的礼物是一个总分最大的飘飘乎数独

输入格式 InputFormat

第一行,两个正整数n m,表示一个n*m飘飘乎数独
接下来一个矩阵,矩阵的每一行数为一个非负数,0表示飘飘乎居士需要用1~m其中一个自然数填充的方格,非0自然数代表已经填充过的方格(即不能够更改的方格)

输出格式 OutputFormat

一行,最后的总分

样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

最优的飘飘乎数独为(并且只存在这一种方案)
1 3 5 2 4
4 1 3 5 2
规定横竖都不能有相邻的自然数,但可以有相等的自然数
得分为第一列 1*(1+4)=5
第二列 2*(3+1)=8
第三列 3*(5+3)=24
第四列 4*(2+5)=28
第五列 5*(4+2)=30
总分为95,也就是最后的答案
对于30%的数据, 保证 3<=n m<=5,0的个数<=10个
对于100%的数据,保证 3<=n m<=7  0的个数<=n*m
数据保证至少存在一个解。

题解

暴力三十分非常高兴

加个剪枝90分。。

f[i]表示不考虑冲突从第i行开始后的所有行能获得的最大分值

如果搜到第i行得分s,且s+f[i]<=ans,就return

正解状压以后写

avatar
  Subscribe  
提醒