P4141 消失之物

基本思路

做\(n\)次计数背包。

当然\(TLE\).

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2020;
int n, m;
int F[N];
int v[N];

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> v[i];
	}

	for (int p = 1; p <= n; p++)
	{
		memset(F, 0, sizeof(F));
		F[0] = 1;
		for (int i = 1; i <= n; i++)
		{
			if (i == p)
			{
				continue;
			}
			for (int j = m; j >= v[i]; j--)
			{
				F[j] += F[j - v[i]];
			}
		}
		for (int i = 1; i <= m; i++)
		{
			cout << F[i] % 10;
		}
		cout << endl;
	}
	return 0;
}

思路改进

从状态转移的过程入手。

从上面的暴力代码也可以看出，所谓不选就是跳过本次外层循环，也就是跳过一系列关于物品\(i\)的动态规划。暴力运用了\(continue\)。

找到跳过的代码

for (int j = m; j >= v[i]; j--)
{
	F[j] += F[j - v[i]];
}

实际上就是跳过了一整次这段代码，即对\(i\)个物品的动态规划更新。

产生思路

既然只是跳过了一次，并没有必要大费周章地再\(O(n)\)跑一整次\(DP\)，针对跳过的这个代码块做文章即可。

可以在所有状态全部更新完之后，枚举不用的背包，针对该层背包，把更新完全部状态的\(F[j]\)受该层背包的影响消除即可。

具体的方法好理解，但是难想出来。

即每次枚举背包时拷贝总答案数组，然后针对该层进行顺序递推减去之前加上的\(F[j - w[i]]\)即可。

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2020;
int n, m;
long long F[N], G[N];
int v[N];

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> v[i];
	}
	F[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = m; j >= v[i]; j--)
		{
			F[j] += F[j - v[i]];
			F[j] %= 10;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		memcpy(G, F, sizeof(F));
		for (int j = v[i]; j <= m; j++)
		{
			G[j] -= G[j - v[i]];
			if (G[j] < 0)
			{
				G[j] = (G[j] + 10) % 10;
			}
			else
			{
				G[j] = G[j] % 10;
			}
		}
		for (int j = 1; j <= m; j++)
		{
			cout << G[j] % 10;
		}
		cout << endl;
	}
	return 0;
}

实现细节

数组拷贝

用到了memcpy这个函数，很方便的拷贝数组。

取模运算

首先还是经典的同余根本不懂，每次运算完后都取模。还有就是考虑负数情况，要先加模数变成整数再取模。