昨天训练时有一道并不难的dp题 http://codeforces.com/gym/103202/problem/H
大意是有n种卡，每种卡有d,k,c三个属性，表示有效时间，使用次数和价格，每张卡可以买任意次，也可以不用卡。再给出m天，用$p_i,q_i$表示一个人要在$p_i$天买$q_i$次东西，问最小代价。
阅读全文
MorphLing
9月 30, 2021
LGV引理给出网格图上两个起点$a_1,a_2$和两个终点$b_1,b_2$，每次只能往右或往上走一步，问$a_1\rightarrow b_1$和$a_2\rightarrow b_2$的所有路径方案中，两条路径没有相交点的方案数
用$e(a,b)$表示从a走到b的方案总数，则$ans=e(a_1,b_1)e(a_2,b_2)-e(a_1,b_2)e(a_2,b_1)$
理解：利用容斥，从$e(a_1,b_1)e(a_2,b_2)$中减去那些存在相交的方案。已知$e(a_1,b_2)e(a_2,b_1)$中每种方案的路径一定相交，对于每个交点，两条路径交点要么在交点处交换位置，要么像是“在交点处反弹了”一样没有交换位置（如下图）
阅读全文
MorphLing
8月 15, 2021