【forge】

【问题描述】

众所周知,小W是一个坏学生,因为熊孩子的本性爆发,所以学习成绩直线下滑。但是小W不知悔改,仍然天天去机房干坏事,这令他的父母很着急。

马上要开家长会了。家长会上会给家长发孩子的成绩单。这是一件令小W很头疼的事情。小W不希望他的家长看到他的真实成绩。突然,一个不好的念头在小W心中萌发了:他要先拿回成绩单,然后在上面添加几笔,把成绩伪造成一个单调不降序列,这样家长才看着舒服。

最近有n次考试,第i次考试的满分为fi,小W考出来的真实成绩为wi。小W知道,在一个数字上面添几笔就可以使它变成另一个数字,比如说,0的上面撇一下就是6,1上面加一横就是7,3左边画两弧就是8.我们用Tij(0<=i,j<=9)来表示这个关系,即Tij=1当且仅当小W可以在数字i上多加几笔把它变成数字j。需要注意的是,Tij不一定等于或不等于Tji。同时Tii(0<=i<=9)这个值并没有什么卵用。

小W希望在成绩单上添加几笔,把成绩变成一个单调不降序列。具体地说,设改动之后的成绩为w1 w2 w3……wn,那么w1<=w2<=w3<=……<=wn。并且,为了不露馅,规定wi<=fi必须成立,且数字不能有前导0.如果有多组解,小W希望改之后他的总分,即w1+w2+w3+……+wn是所有方案里面最高的。这对一个坏学生来说不是一件简单的事情,于是他找到了你。

你本来不想帮助小W干坏事,但是熊孩子的软磨硬泡不是任何人都受得了的。现在这个任务就交给你了。

【输入格式】

输入文件的第一行是一个整数n。

接下来n行,每行2个正整数fi和gradei代表第i次考试的满分与小W的真实成绩。

接下来10行,每行10个数,不是0就是1。第(i+n+2)行的第(j+1)个数表示Tij。

【输出格式】

输出文件的第一行包含一个字符串。如果存在这样的方案,那么输出YES,否则输出NO。

如果你的输出时YES,那么第二行包含n个整数w1 w2 …… wn。

【输入样例1】

2
7 3
2 2
0 1 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0

【输出样例1】

YES

2 2

【输入样例2】

2
9 8
7 6
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

【输出样例2】

NO

【数据范围】

n≤10000 gradei、fi≤10的50次方

首先,对于T数组可以跑一遍Floyed判断数字间的转换情况。

正向构造单调不降序列很麻烦,注意到题目有要求满足条件的方案中和最大的要求,那么我们可以考虑反向构造一个单调不上升序列,再来考虑每一位的限制。

对于一个满分为3000的考试,改法有两种,1是把最高位改成3,这时后面几位自然必须为0,2是把最高位改成1或2,此时后面无论怎么改都不会超过这个界限,为了让后面的数尽可能大,我们可以贪心的取每一位为限制的最大值来验证能否成立,这个过程DFS实现,每次记录时候选到了限制数字即可。最后得出的ans[i]还要与下次的考试满分成绩作比较选较小值作为limit。如果这样选都出现了前导0那么一定是不合法的情况。另外对于当前成绩位数大于限制成绩为位数的话,那么无论怎么改都不可能成立,输出NO即可,对当前成绩位数小于限制位数的情况,每一位选最大即可。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*