[luoguP2221] [HAOI2012]高速公路（线段树）传送门考虑每一段对答案的贡献用每一段的左端点来表示当前这一段，那么区间就变成了[1,n1]如果询问区间[l,r]，其中一个点的位置为x，则它对答案的贡献为(xl)*(rx)*s[x]（s[x]为这一

[POJ2151]Check the difficulty of problems（概率DP）传送门每个队之间是独立的f[i][j]表示当前队伍前i个题答对j个的概率满足条件的概率 == 全部方案（除去答对0）的概率 不满足条件的概率（每个队伍答对1~n1）#include <cstdio>#incl

[BZOJ1419] Red is good（期望DP）传送门逆推只不过顺序还是顺着的，思想是逆着的f[i][j]表示还剩下i张红牌，j张黑牌的期望值那么边界是f[i][0]=i，因为只剩i张红牌f[0][j]=0，只剩黑牌，显然直接停止最优f[i][j] = ma