『完全背包+线性DP』画山

本文主要是介绍『完全背包+线性DP』画山，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

在这里插入图片描述

题解

如果不是输出本质不同，我们只需要设fi][j]表示画到了位置(i,j)的方案数。

很容易得到状态转移方程： $f[i][j]=\sum_{k=1}^{p} f[i-a_k][j-b_k]$

现在考虑如何解决本质不同的问题。

我们发现对于每一个点，相同斜率转移过来的长度不能重复，那么我们只需要对每一个相同斜率的不同长度进行转移即可。那么怎么得到这些斜率相同长度不同的线段呢？我们只需要对那些斜率相同的线段的长度做完全背包即可。

我们设 $f [i] [j] [k]$ 表示到了位置(i,j)且选择的斜率为k的方案书。我们另 $s[i][j]=\sum f[i][j][k]$ .那么就有：
$f[i][j][r]=\sum_k f[i-a_k][j-b_k][t],\frac{a_t}{b_t}\not =k\\=\sum_k s[i-a_k][j-b_k]-f[i-a_k][j-b_k][r]$

注意：这里的 $a$ 和 $b$ 值是完全背包处理出来的结果。

随后输出 $s [n] [0]$ 即可，初始化 $s [0] [0] = 1$ .

代码如下：

#include <bits/stdc++.h>using namespace std;
const int N = 200;
const int P = 1e9+7;int n, m, p, k = 0;
int g[N], x[N], y[N], f[N][N][N], s[N][N];
struct node {int x, y;
} a[N];
vector <int> c[N];bool cmp(node p1,node p2) {return 1.0 * p1.y / p1.x < 1.0 * p2.y / p2.x;
}void Bag(int l,int r,int num)
{g[0] = 1;for (int i=1;i<=n;++i)g[i] = 0;for (int i=l;i<=r;++i)for (int j=a[i].x;j<=n;++j)g[j] |= g[j-a[i].x];for (int i=1;i<=n;++i)if (g[i] == 1) c[num].push_back(i);return;
}void init(void)
{sort(a+1,a+p+1,cmp);int j = 1;for (int i=1;i<=p;i=j+1){for (j=i;j<=p;++j){if (a[i].x * a[j].y ^ a[i].y * a[j].x) {j --;break;}}x[k+1] = a[i].x;y[k+1] = a[i].y;Bag(i,j,++k);} return;
}void DP(void)
{s[0][0] = 1;for (int i=1;i<=n;++i)for (int j=0;j<=m;++j)for (int K=1;K<=k;++K) {for (int t=0;t<c[K].size();++t)  {int nx = i - c[K][t];int ny = j - c[K][t] * y[K] / x[K];if (nx < 0 || ny < 0) continue;if (nx > n || ny > m) continue;(f[i][j][K] += s[nx][ny]-f[nx][ny][K]) %= P;}(s[i][j] += f[i][j][K]) %= P;}cout<<(s[n][0] + P) % P<<endl;return;
}int main(void)
{freopen("paint.in","r",stdin);freopen("paint.out","w",stdout);scanf("%d %d %d", &n, &m, &p);for (int i=1;i<=p;++i)scanf("%d %d", &a[i].x, &a[i].y);init();DP();return 0;
}