二模 (7) day2

时间:2020-12-15 15:06:20

第一题:

题目大意:多重背包。

解题过程:

1.二进制拆分。最慢的点0.5s。

2.单调队列优化会更快,不过我不会。。


第二题:

题目描述:给定一个n×m的矩阵,记录左上角为(1,1),右下角为(n,m),现在从(1,1)开始取数,每次只能向下或向右移动一个单位,最终到达(n,m),我们把路径上所有的数相乘,结果记为C。使C的结果最大已经不能满足我们了,现在我们想让C末尾的零个数最少。

解题过程:

1.NOI导刊上的老题了。。结论都记着了。。只要做2次dp。F[i][j] , g[i][j] 分别表示走到(i,j)2最少, 和 5最少。

答案就是min(F[n][m],g[n][m])

2.记住了结论感觉有些不厚道,下面给出证明:

A:首先证明答案不会小于min(F[n][m],g[n][m]):假设答案不是 min(F[n][m],g[n][m]) ,设最优路径上有x个2,y个5,那么答案就是min(x,y)。而min(x,y)>= min(F[n][m],g[n][m])。

B:然后来证明 存在末尾0的个数为min(F[n][m],g[n][m])的路径。。设F[n][m]对应的路径上有x1个2,y1个5。

g[n][m]对应的路径上有x2个2,y2个5。

那么F[n][m]对应的路径上末尾0的个数为min(x1,y1). g[n][m]对应的路径上末尾0的个数为 min(x2,y2);

min{ min(x1,y1) ,  min (x2,y2) } = min{x1,y1,x2,y2}.

因为 x1<=x2,y1>=y2  所以 min{x1,y1,x2,y2} = min{x1,y2}=min{F[n][m],g[n][m]};  证明完毕。


第三题:

题目大意:对于排列(P1,P2,P3,…Pn),定义(i,j)为逆序对当且仅当i<j且Pi>Pj。统计{1,2,3,…,n}的所有排列中,逆序对数量为m的排列个数。 0<n,m≤1000。

解题过程:

1.看到数据范围,八成就是O(N^2)的dp了。就尽量往dp的方向去想。假设现在有一个最大数为A的排列,逆序对数数有p个。 那么就可以 把它加一个 数字 A+1,得到最大数为A+1的排列,根据A+1的位置的不同,可以得到逆序对数不同的A+1的排列。

2.把上面的思路倒过来,很容易得到状态转移方程:设F[i][j]表示1~i的排列中逆序对数有j个的 有多少个。

F[i][j]=sum(F[i-1][i-j+1 .... j]);  注意i-j+1<0的时候, F[i][j]=sum(F[i-1][0.... j]); 复杂度O(N^3);

3.再用一个前缀和数组维护,就把复杂度降到了O(N^2): sum[i][j]  =  sum(F[i][0...j]);

那么方程就变为 F[i][j]=sum[j]-sum[i-j]; 同样 i-j<0的时候, F[i][j]=sum[j].