网站建设部岗位职责,软件开发文档范例,商城网站建设论坛,丰台区网站建设100分数310 ———————————————————————————————————— 期望值#xff1a; |T1#xff1a;100/T2#xff1a;10/T3#xff1a;100/T4#xff1a;100 ————————————————————————————————————… 100分数310 ———————————————————————————————————— 期望值 |T1100/T210/T3100/T4100 ———————————————————————————————————— 实际 |T1100/T210/T3:100/T40what the fuck ———————————————————————————————————— 讲题前T1100/T2100/T3:100/T420少加了个大于号呵呵呵呵呵呵呵呵呵呵呵呵了。 ———————————————————————————————————— 讲题后AK ———————————————————————————————————— 废话不多说开始讲题。 xc说要像讲故事一样 T1呵呵比较水吧95.5percent的人做对了。 题解分界线—————————————————— 此题一开始设一个-2到100的数组然后初始化f[0]:1。 f表示跳到第i个阶梯有多少总方案。 于是就从裤兜里拿出神器——动态规划。因为跳到第i层可以从i-1层、i-2层、i-3层跳过来所以dp方程式就是f[i]:f[i]f[i-1]f[i-2]f[i-3]。再判断一下第i层可不可行会不会掉下去就可以了如果会掉下去就把第i层改成0种方案输出f[n]。 T2描述其实要很细致地读题才会明白小细节。各种坑 细节1此题不想八皇后一样八个方向此题只有4个方向。 细节2此题有许许多多的坑坑洼洼不可以放不明石像于是就要额外判断。 细节3心胸狭窄的石像们无法容忍自己位置下方x格的右侧y格有其他的石像于是还是要额外地判断。 不怕时间超限的方法很多人想到一个双重循环来枚举每一个格子当然时间超限…你不需要双重只需要用一个for来枚举每个格子的纵列可不可以放然后每次递归一个第几行就OK了。 接下来就是加上不怕超限的方法按照题目细节描述来模拟a。 T3规律题。 我们发现输出的行数是n-1*2行。 于是我们来分成两个部分来探讨规律—— 第一个部分就是第1行到第n-1*2-4行。 用样例数据来看 XXXXXXOOOOOO__ XXXXX__OOOOOXO XXXXXOOOOO__XO XXXX__OOOOXOXO XXXXOOOO__XOXO XXX__OOOXOXOXO 这是前6行。第一行的X个数为6紧跟着6个O然后是空格。 第二行就是把第6个X换到空格位置1里XXXXX()OOOOOO(X) 把第1个O换到空格位置2里XXXXX_(_)OOOOOX(O) 神奇的发生了复制别怪我 第三行的X个数为5紧跟着5个O然后是空格加上1个“XO”。 第四行就是把第5个X换到空格位置1里XXXX(_)OOOOO(X)_XO 把第1个O换到空格位置2里XXXX_(_)OOOOX(O)XO …… 到了第二个阶段就是 XXXOXOO__OXOXO X__OXOOXXOXOXO XOXOXO__XOXOXO __XOXOXOXOXOXO 第一段XXX__OOOXOXOXO里的XXX(__)OO(OX)OXOXO互换。 第二段XXXOXOO__OXOXO里的X(XX)OXOO(__)OXOXO互换。 第三段X__OXOOXXOXOXO里的X(__)OXO(OX)XOXOXO互换。 第四段打表就对了。 T4使用吕乐大大的树形dp方法时超80打表研究之后AK** 正解转大叔的题解别打我 先建立一个s数组s[i,j]表示从第i个到第j个的和求和时因为可能ij-1会大于n就是会回头那就是一种特殊情况自己想想就好了然后f[i,j]表示第i个到第j个的最小能力和最后答案就是min(f[i,n])意思是对于每个i来说最小的f[i,n]且f[i,n]非零。 for i:2 to n dobeginfor j:1 to n dobeginfor k:1 to i-1 dobeginr:jk;if (jkn) then r:(jk) mod n; if (f[j,i]f[j,k]f[r,i-k]s[j,i]) or (f[j,i]0) thenf[j,i]:f[j,k]f[r,i-k]s[j,i];end;end;end; AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAKKKKKKKKKKKKKKKKKKKKKKKKKKK啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦啦 转载于:https://www.cnblogs.com/RainbowCrown/p/11148474.html
