Day4

luogu p1058

​ 一道大模拟,第一次做传说中的“打表"题,好刺激!!

题意

​ 给出一个n*m的矩阵,代表n*m个小方格,每个矩阵元素都是正整数,代表对应方格有几个正方体,现在要求把整个由n*m“方格”组成的图画出来。

思路

打表记录一个正方体,然后由于观察视角是右上方,所以从左向右,从下往上,从后往前进行画图覆盖。

luogu p1328

​ 一道水题,水的一B。

luogu p1062

​ 考察二进制,注意爆int

luogu p1201

​ 又是一道水题

luogu p1108

​ 考察LDS,以及路径条数

题意

​ 给出一段序列,求出最长下降子序列,并且输出最长下降子序列条数。

思路

​ 先扫一遍LDS,然后对于路径数再次dp,dp核心是假设f[i]表示以结尾的序列的路径数,且对于j<i,以j结尾的序列不存在重复序列

​ if(d[i] == d[i-1]+1 && a[i] < a[i-1] ) f[i] += f[j];

​ if(d[i] == d[j] && a[i] == a[j] ) f[j] = 0;

​ // 由于f[i] 是 由f[i-1]推导而来的,故而由归纳法,只需满足添加f[i]的时候仍然满足假设即可。

原文地址:https://www.cnblogs.com/backkom-buaa/p/11478682.html