二维DP写法
#include <iostream>
using namespace std;
const int N = 103, M = 1e5 + 3, MOD = 1e9 + 7;
int n1, n2, m;
int f[N][M], p[N];
int main()
{
cin >> n1 >> n2 >> m;
for (int i = 1; i <= n1 + n2; ++i)
cin >> p[i];
for (int i = 0; i <= n1 + n2; ++i)
f[i][0] = 1;
for (int i = 1; i <= n1; ++i)
{
for (int j = 0; j <= m; ++j)
{
if (j >= p[i])
f[i][j] = (f[i - 1][j] + f[i][j - p[i]]) % MOD;
else
f[i][j] = f[i - 1][j];
}
}
for (int i = n1 + 1; i <= n1 + n2; ++i)
{
for (int j = 0; j <= m; ++j)
{
if (j >= p[i])
f[i][j] = (f[i - 1][j] + f[i - 1][j - p[i]]) % MOD;
else
f[i][j] = f[i - 1][j];
}
}
cout << f[n1 + n2][m] << endl;
return 0;
}
降至一维写法
#include <iostream>
using namespace std;
const int N = 1e5 + 3, MOD = 1e9 + 7;
int n1, n2, m, p;
int f[N];
int main()
{
cin >> n1 >> n2 >> m;
f[0] = 1;
for (int i = 0; i < n1; ++i)
{
cin >> p;
for (int j = p; j <= m; ++j)
f[j] = (f[j] + f[j - p]) % MOD;
}
for (int i = 0; i < n2; ++i)
{
cin >> p;
for (int j = m; j >= p; --j)
f[j] = (f[j] + f[j - p]) % MOD;
}
cout << f[m] << endl;
return 0;
}
爱你,找的就是二维的,一维的对我来说理解有点困难