noip做题笔记

1. P2822

用帕斯卡定理递推组合数，递推的时候判断是否为k的倍数，然后利用二维前缀和。这些都想到了，但是判断为k的倍数被难到了，因为直接把所有的组合数求出来显然会爆long long，需要模一个数。想到这就没头绪了。看到题解恍然大悟，可以直接模k，为0即为k的倍数，并且可以很好地与递推结合

2. P1450

上来就写了一个类似多重背包的dp，虽然复杂度很大，但还是希望能骗到一定的分数，然后全都tle了...

看了题解之后发现是容斥

我们首先可以预处理出没有数量限制的情况，也就是完全背包
然后再减去不符合要求的情况。先考虑有一种硬币不符合要求，不符合要求的方案数为 $dp[s-(d_i+1)*c_i]$ 。可以看作：我先强制选择 $d_i+1$ 个硬币，这样之后不管你怎么去选硬币，都是不符合条件的。

再应用容斥原理即可

3. *P5664

容斥、dp

因为每列选择有限制，所以考虑容斥。首先考虑总方案数

$$g_{i,j}=g_{i-1,j}+s_i*g_{i-1,j-1}$$

（$s_i$表示第i行数的总和）

表示前i行选了j个数的总方案数

然后考虑不合法方案数,对每一列（记枚举到的列为col），都有

$$f_{i,j,k}=f_{i-1,j,k}+a_{i,col}*f_{i-1,j-1,k}+s_i*f_{i-1,j,k-1}$$

表示前i行，在当前列选择了j个，在其他列选择了k个的方案数
这样做的复杂度是 $O(mn^3)$ 的。实际上我们不关心j和k的具体数值，所以可以简化状态

$$_{i,j}=f_{i-1,j}+a_{i,col}*f{i-1,j-1}+s_i*f_{i-1,j+1}$$

表示前i行，当前列选择个数比其他列多j个的情况

4. P1279

字符串距离型dp

状态转移方程：

$$f[x][y]=min(f[x-1][y]+k,f[x][y-1]+k,f[x-1][y-1]+abs(a[x]-b[y]))$$

初始化：

$f[0][i]=f[i][0]=k*i$

注意i可以取到0，即 $f[0][0]=0$

相似题目：P1140、P2758、P2268

5. P1717

一开始把状态设成 $f[i][j]$ 表示第i个分配j个单位时间最多收益。很显然不符合动态规划的特点，走火入魔了属于是

i的含义应该是前i个池塘

状态转移方程：

$$dp[i][j]=max(dp[i-1][j-t[i-1]-k]+f[i]+(f[i]-1*d[i])+(f[i]-2*d[i])+...+(f[i]-(k-1)*d[i]))$$

k是分配给当前第i个池塘的单位时间

k的取值范围：$j-t[i-1]-k>=0$ 且 $f[i]-(k-1)*d[i]>=0$

利用等差数列求和公式，得到

$$dp[i][j]=max(dp[i-1][j-t[i-1]-k]+k*f[i]-\frac{k(k-1)}{2}d[i]$$